# Questions tagged [bit-strings]

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

10 questions
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 ...
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 ...
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)$ ...
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 ...
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 ...
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$ ...
Given XOR values of 3 indices how can we find the numbers? Like say if I have indices from 1 to 7, how can I find the numbers by given XOR values? I have: $X_{1} \oplus X_{3} \oplus X_{5}=V_1$ $X_{1}... 4answers 1k views ### Find a recurrence relation for the number of bit strings of length n that do not contain “0011” So this is what I thought: i) start with 1:$f(n-1)$ii)start with 01:$f(n-2)$iii) start with 000 :$f(n-3)$iv) start with 0010:$f(n-4)$Though I was told it's not true. I would like to know ... 1answer 56 views ### counting set bits of a natural number For a natural number$n$let$f(n)$denote the number of set bits of$n$- which is basically the Hamming weight of the binary representation of$n$. See wiki for more info. I have to prove that$f(n^...
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 ...