# 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. ...
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?...
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 ...
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

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 ...
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 '...
1k views

I am stuck with this combinatorics problems - Let $n$ be a positive integer and let $b_{n}$ denote the number of compositions of $n$ into $k$ parts, where each part is one or two. For example, $(1, 2, ... -2 votes 2 answers 39 views ### Determining Big O Method The image attached contains a sorting problem and its solution. I'm having a hard time understanding the very last bullet point of the solution in determining Big O. Why do we need to compare as well ... 1 vote 1 answer 59 views ### What would the notation for this binary string look like? Every block of 1's of length$\ge 4$cannot be followed by a block of 0's of length$\ge 4$, and any block of 1s of length 1, 2 or 3 must be followed by a block of 0s whose length is congruent to 1 ... 1 vote 0 answers 65 views ### A de Bruijn sequence of infinite length? A de Bruijn sequence is a (typically) binary string of length$2^k$which contains every binary string of length$k$as a substring exactly once, if you allow it to wrap around. For example, ... 0 votes 0 answers 23 views ### What am I missing here? Basic Bit Operation Consider the bit strings$A=001100$and$B=010101$then$A\vee B= ? $($B=$bitwise NOT) First I wrote$B$and get, $$B= 101010$$ then I took first "$0$" of$A$and "$1$" of$B`$then get (1), ... 0 votes 1 answer 49 views ### Boolean expression for a problem I want to express problems like this in boolean expression with say$XOR$, or operations etc.$HD$= Hamming distance Say for$HD(2^4, 0000)\geq2\;$the boolean expression is $$x1 (x2+x3+x4) + x2 (... 0 votes 1 answer 57 views ### What's this compression technique called? Consider this string of 1's, 0's (spaces added for readability): 1010 1010 1010 1010 We can ... 0 votes 1 answer 35 views ### Why does this Boolean formula F always evaluate to zero given input x'? Let \oplus mean the exclusive OR operator, I have this boolean formula F which takes inputs x, where given |x|=n, we have:$$x:\{a_1,a_2,a_3,...,a_{n/2},b_1,b_2,b_3,...,b_{n/2}\}$$and the$...
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 ...