Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [bit-strings]

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

5
votes
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 ...
2
votes
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 ...
1
vote
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)$ ...
6
votes
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 ...
10
votes
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 ...
4
votes
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$ ...
1
vote
4answers
482 views

Finding numbers by given XOR values.

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}...
2
votes
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 ...
1
vote
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^...
0
votes
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 ...