# Questions tagged [bit-strings]

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

124 questions
Filter by
Sorted by
Tagged with
21 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 ...
43 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 ...
29 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 '...
124 views

13 views

### Field on 3 bit-string set with uniformly distributed mapping.

I'm wondering if it's possible to construct a set S consisting of three bit-strings and some uniform mapping F: S x S -> S (...
36 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 ...
27 views

### Maximize the entropy of Hamming distance

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 ...
10 views

### Semi-metric on bit strings and degree of Cauchy-Schwarz inequality

Given elements $x,y \in GF(2^m) ,$ (e.g., bit strings of the form $x =011010, y= 110100$ for $m=6$), we define a semi-metric $d(x,y)$ by the largest distance between bits in $x,y$ that disagree. For ...
62 views

33 views

### Is the prefix of power of three in binary representation contains all possible number combinations?

Let $S(x)$ be the string of positive integer $x$ in binary representation. Conjecture: For any positive integer $x$, there exists an integer $k$ such that string $S(x)$ is a prefix of string $S(3^k)$....
301 views

### How many bit strings contain exactly five $0$s and fourteen $1$s if every $0$ must be immediately followed by two $1$s?

How many bit strings contain exactly five $0$s and fourteen $1$s if every $0$ must be immediately followed by two $1$s? What I need help with: For this question, the answer is 126-bit strings. ...
73 views

### Thue-Morse Sequence riddle

The Thue-Morse sequence is constructed by replacing each instance of $0$ with the string $01$, and replacing $1$ with $10$. Equivalently, we can construct the sequence by successively appending the ...
43 views

### Entropy conservation of binary functions

In the merge function from https://github.com/ifdefelse/ProgPOW the authors talk about entropy maintaining functions that operate on bit-strings. Can someone explain what this is? I found literally ...
52 views

### How long can a string be before it must have considerable repeated substrings?

A considerable repeated substring $t \leqslant s \in \Sigma^*$ is a string of length $2$ that occurs at least 3 times disjointly within $s$ or a string of length $3$ or more that occurs at least $2$ ...
37 views

I was reading an article where they have stated the following. Can someone explain how the L-notation is being calculated as 122. Thanks in advance.
296 views

### Number of binary words that can be formed

How many binary words of length $n$ are there with exactly $m$ 01 blocks? I tried by finding number of ways to fill $n-2m$ gaps with $0$ and $1$ such that no $'01'$...
117 views

### Generating combinations using a butterfly network

I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming ...
91 views

68 views

### How many bitstrings of length 10 have the following property:

How many bitstrings of length 10 have the following property: a) sum of first $5$ bits are $3$? b) sum of first $5$ bits equals sum of last $5$ bits? c) the bits are written in increasing order (no ...
31 views

### How many strings of n bits are there which differ by exactly m bits?

For example: If n = 8 and m = 0: ans = 1 If n = 8 and m = 1: ans = 8 If n = 8 and m = 2: ans = ? If n =256 and m = 3: ans = ?
186 views

224 views

### Counting number of Bitstrings that do not contain $110$ for length $n \ge 4$

Question: Consider bitstrings that do not contain $110$. Let $S_n$ be the number of such strings having length $n$. What is $S_n$ for $n \ge 4$? Answer: $S_n = S_{n-1} + S_{n-2} + 1$ Attempt: I ...
52 views

### Perfect matching in the n-unit-cube, Is hyperplane statement wrong?

I was thinking about perfect matchings in the graph of the unit-cube of dimension $n$: $Q_n = [0,1]^n$. ($0$-$1$-strings of length n are vertices. Two of such are connected by an edge iff. they differ ...
### Formula to get result as $0$ for a variable assigned as $1$.
I actually want to perform bitwise not operating in normal calculation mode in my Casio fx-991 ex. I want a formula which consists of one variable, which can be assigned with either $0$ or $1$. The ...
If $x = a$ xor $b$, given the values of $x$ and $a$ can we find $b$? In other words, which function can be applied on both sides in the equation to get the value of $b$?