# Questions tagged [bit-strings]

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

199 questions
Filter by
Sorted by
Tagged with
256 views

### Counting bit strings with given numbers of higher-order bit flips

Background information Bit flips Given a bit string, we say that bit flip happens when $0$ changes to $1$ or $1$ changes to $0$. To find bit flips, we can shift the string by $1$ and xor that new ...
80 views

78 views

### How many bitstrings of length n contain 3 consecutive ones ("111")?

I tried creating a recurrence formula. Can someone evaluate it? a(n) =a(n-1)+2^(n-3)+a(n-3) 0-> followed by bitstring of length n-1 (represented by a(n-1)) 1->10->101; 1->10->100; 1->...
119 views

### What's the minimum guaranteed substring match between a binary string and a chosen rotation?

Given $n$: An adversary chooses a binary string $X$ of length $n$. I choose two distinct rotations of $X$, called $Y$ and $Z$, with the goal of maximizing $m$, the length of the longest prefix shared ...
1 vote
52 views

### What are the mean and standard deviation of the convolution of two bit vectors?

I'm cryptanalyzing a cipher I've written, which takes a message of arbitrary size and returns a message of the same size. Because of the rotBitcount operation, ...
• 121
1 vote
77 views

### How can I calculate the orbit of a group action of a group generated by one element?

I have a bit string, $X$, of $n$ bits. I am applying an operation, $g$, which involves a permutation of the bits and then flipping the first $k$ bits. I have a proof that the $g$ generates a group ...
• 873
42 views

### Number of bitstrings of length 18 that have consecutive 1's — why is my solution wrong?

Consider bitstrings of the pattern 11....(16 dots). There are a total of 2^16 such bitstrings. Now consider the pattern 011.....(15 dots). It is clear that this pattern and the previous pattern don't ...
• 330
1 vote
62 views

• 103
1 vote
37 views

### Expected number of random bitstrings that match a certain prefix

I am faced with the following problem. Assume I generate $N$ random bitstrings of length $L$ without replacement, that is, no duplicate bitstrings are allowed. Now let $p$ be an arbitrary, but fixed, ...
• 161
50 views

### At most $k$ contiguous $\mbox{true}$ values in a Boolean array using SAT

Given an integer $k > 0$ and a Boolean array $A$ of length $n$, find a simplified and efficient CNF formula to ensure that there is not more than $k$ contiguous $\mbox{true}$ values in this array. ...
• 1,264
62 views

### How many n-bit strings are unbalanced?

I am stuck on this question that i came across in my assignment. What does it mean by unbalanced string? I don't know the proper approach of solving this question How many n-bit strings are unbalanced?...
• 11
119 views

### Unique-xor sets

Let a set $S$ of nonnegative integers be a "unique-xor" set if all pairs of distinct integers in $S$ have different bitwise xor from all other pairs. Let $x(n)$ be the least maximum element ...
• 957
35 views

### Bitstring counting with three elements

A bitstring (length $10$ $\{0,1\}$) has exactly $120$ string that contains three $0$s, but now I am trying to find out how many strings with three zeroes if the string looks like this: $\{0,1,\phi\}$. ...
1 vote
82 views

### Why is $\lim_{b \rightarrow 1} concat_b(x,y) \ne x+y$ for base-$b$?

Let $x=x_N\ldots x_0$, $y=y_M\ldots y_0$ be integers with base-$b$ digits $0 \le x_i,y_j < b$. Concatenate them via x \otimes_b y\triangleq x_N\ldots x_0 y_M\ldots y_0=b^{len_b(y)}x+y=b^{1-\{\...
• 1,447
1 vote
119 views

### Find the XOR of every other number in a given range

Lets say that R=15 and L=8, then how can I efficiently find: 15 XOR 13 XOR 11 XOR 9 If R=20 and L=10, then it would be: ...
• 145