# Questions tagged [bit-strings]

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

156 questions
Filter by
Sorted by
Tagged with
33 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,242
21 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
42 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 ...
• 645
19 views

### Bitstring counting with three elements

A bitstring (lenght 10 {0,1}) has exactly 120 string that contains three 0s, but now I am trying to find out how many strings with tree zeros if the string looks like this: {0,1,φ}. Can I still use ...
51 views

### Is standard deviation an associative operation? How does this affect the use of a combiner?

The mean µ of a set of numbers X = {x1, x2 ... , xn} is defined as: enter image description here The standard deviation σ of a set on numbers X is defined as: enter image description here
1 vote
78 views

• 303
1 vote
82 views

### How to optimize subset sum problem through bitmask with the option to generate indices?

I was solving the subset-sum problem. There are many ways to solve the problem but I prefer the bitmask approach which is explained here. Now If I want to get the index of the elements that form my ...
• 71
57 views

### How many different ways a string of '$n$' length can be divided into '$r$' number of non-overlapping non-empty segments?

I was trying to figure out some computation regarding string operations. Suppose, I have a string of length $n$ and I want to split the string into $m$ number of non-overlapping segments. How many ...
1 vote
31 views

### Semigroup of bit-string substitutions - any pointers?

Consider a pair $s=(s_0,s_1)$ of bit-strings (strings of 0s and 1s). Let $s$ act on a bit-string $b$ by replacing every $0$ in $b$ by $s_0$ and every $1$ in $b$ by $s_1$. Then the set $S$ of all such '...
• 11
1k views

• 705
45 views

### Finding the number of bit sequences without using recursion

How many 8-bit strings without three consecutive 1's are there that start with 1? I used recursion and found that the answer is 68, but this was asked in a high school test so I am looking for an ...
• 459
We have a set of possible "key"s represented by bitstrings of length $k$. For example, when $k=3$, it can be $S = \{001, 010, 011, 000, 111\}$. I would like to find a "guess", which maximizes the ...