# Questions tagged [bit-strings]

Use this tag for questions related to array data structures that compactly store bits.

10 questions
4answers
341 views

### Number of q-ary strings of length m which do not contain k consecutive zeros

A finite q-ary-alphabet is given $$A_q = {0,1,2,...,q-1}.$$ Now I am considering the set of all finite strings over the alphabet $A_q$. I am interested on the number $$N(m,k)_{A_q}$$ of strings of ...
2answers
2k views

### Bit flipping algorithm

The goal is to flip all the bits in the same direction (I mean all to be 1 ) For example, we have: 0110011 We need to flip the bits so that we get 1111111 We can only flip K consecutive bits at a ...
1answer
49 views

### Bit swapping probability question

Let $x = x(1), \dots , x(n)$ be a bit string containing exactly $m$ occurrences of 1. Consider the following operation on $x$: we choose a random pair of indices $(i,j),$ and we swap $x(i)$ and $x(j)$ ...
2answers
246 views

### Count number of exact matching sequences

Consider all pairs of binary strings $P$ and $T$. Let the length of $P$ be $n$ and the length of $T$ be $2n-1$. For each such pair, we can check if $P$ is exactly equal to each of the $n$ substrings ...
1answer
581 views

### Counting Binary Strings (No block decompositions)

The main question goes : How many binary strings of length $n$ are there that do not contain an odd string of $0$'s as a maximal substring? (So $1001$ is okay but $10001$ is not) A maximal ...
2answers
360 views

### Number of binary and constant-weight strings of length m which do not contain k consecutive zeros

I am considering the set of all finite and binary strings. In the following I am interested on the number $N(m,k,r)$ of strings with length $m$ and Hamming weight $r$ which do not contain $k$ ...
4answers
482 views

2answers
261 views

### Counting the number of bit strings containing a substring

Consider a general bit string of length $n$; how many bit strings are there that contain a substring $T$? For example, given a bit string of length 6, how many are there that contain $110$ as a ...