# Questions tagged [bit-strings]

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

90 questions
98 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 ...
37 views

40 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 ...
479 views

21 views

### Is there a prefix-free language that can encode any other prefix-free language with at most a constant overheard?

Let $U$ and $P$ be prefix-free languages with alphabet $\{0,1\}$. We say that $U$ can encode $P$ with at most a constant overhead if there exists an injective function $c:P \to U$ and a constant $a$ ...
16 views

### Binary Rotation in Hilbert Curve?

Currently, I am following this guide to try and code up a function for the Hilbert Curve, however, I am stuck on the rotation step. I am a computer science student with not much a mathematical ...
93 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 ...
26 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 ...
30 views

### 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 ...
59 views

### Preserving the bitwise dot product distributive property

We can define the bitwise dot product as the dot product between the vectors of the binary bit representations of two numbers. E.g. $$5\cdot 7 = (1,0,1)\cdot(1,1,1) = 2$$ But curiously, this dot ...
57 views

### Inverse operation of xor

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?
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 ...
53 views

### Bit flipping algorithm implementation or psuedo-code

I am trying to understand and implement Bit flipping algorithm Can someone share the psuedocode for the algorithm and explain in detail? I cannot understand the answer. I also want to understand ...
105 views

### Enumeration of Binary Strings

Suppose we want to encode the natural numbers as bit strings as follows: ...
49 views

### Is there a name for the set of “unique” combinations of the powerset of $2^n$ modulo permutation?

I was studying an algorithm on $k$-combinations of $n$-bit strings and realised that, my brute-force approach would spend lots of time on "structurally equivalent" bitstring combinations, that could ...
49 views

### Probability that a bit sequence does not appear in a sequence

Find the probability that a bit sequence $X$ of length $2k$ does not appear in a randomly generated bit sequence of length $n\geq 2k$. If for the general case it is hard, let's solve it for the ...
90 views

### How to get the operand for the bitwise operator of finding remainder

Sorry if this sounds offtopic, but I will try to phrase the problem in such a way till it’s an arithmetic problem. As part of a hardware MIPS assembly assignment, I have to find the mask for the andi ...
47 views

### Find the probability that all triples of bits in a byte will not contain binary digits of only one type?

Find the probability of the situation where we have 1 byte(8 bit) and there are no any 3 equal bits sequence in this byte. All values of the byte are equiprobable. I`ve tried to find the inverse ...
25 views

### Total number of bit-strings that start with 3 ones and end with 2 ones

I have a problem where I need to find the total number of bit-strings with the length of 30 that start with 3 ones and end with 2 ones. The total number of 1s in the string is 17 and the total number ...
2k views

### Logic behind bitwise operators in C

I came across bitwise operations in C programming, and I realized that XOR operator can be used to swap 2 numbers in their binary bases. For example let i=(65)_{10}=(1000001)_{2}, \text{ and } j=(...
69 views

### How long message can I send?

I know the $n$-bit message ($M$). I have to send it to the receiver bit by bit. For each bit I can also send one bit of comment ($C$). Before receiver gets the bit, he have to guess it($G$). After ...
173 views

### Combinatorics problem with bit-strings [closed]

When only three types of bit strings 0, 10,11 are available, how many valid $7$-bit strings ...
49 views

### reference request - Practice problems for probability theory.

I need some good probability theory practice problems on the following topics - Binary strings ( Bit strings ) generating random permutations using bit strings Coin toss problems where each toss is ...
71 views

### What is the name of $(\mathbb{Z}_2^s, \oplus, \odot)$ and where is it studied?

I'm studying the ring $(\mathbb{Z}_2^s, \oplus, \odot)$, where $s$ is arbitrary, $\oplus$ is the sum modulo $2$, and $\odot$ is the AND. Does it have a name? Even for a certain fixed $s>1$? Does ...
80 views

### Does the Hamming weight of $n \to \infty$ diverge or converge?

The Hamming weight (or population count) of an integer $n$, which we denote by $w_H(n)$, is the number of $1$'s in the binary expansion of $n$. For example, let $n = 25_{10} = 11001_2$; counting the ...
78 views

### Bias-free adjustment of random bit strings

Let's say you have a source of random bit strings, which can generate a bit string of any length where each bit is independently set with fixed probability $p$, which I'll call my $p$-source. Now ...
61 views

### entropy of binary strings showing a beta-distribution hamming distance

Let's define a binary string random variable of length $n$, i.e., $X\in \left\{0,1\right\}^n$. Let us define $D$ as the random variable obtained as the Hamming distance between two samples of $X$ $x_1$...
93 views

### Bitstrings and set of solutions

There is something about counting bitstrings and the format of the solutions I didn't really understand yet. Given a bitstring problem that asks to elementarily count how many bitstrings of length 36 ...
43 views

### Combinatorics question about binary string

There exist a 20-digits sequence consists of 10 zeros and 10 ones. What is the number of combinations in which no three consecutive zeros are in the sequence. The answer provided is 24068, and has ...
23 views

### How many different strings of length $100$ may be composed of $10$ different $10$ position binary numbers?

"How many different strings of length $100$ may be composed of $10$ different $10$ position binary numbers?" So this series would be divided into $10$ segments of $10$ bits. Maximum number of options ...
176 views

### Find a recurrence relation for a quinary string with NO consecutive zeros

For n ≥ 0 let a(n) be the number of quinary strings (only contain digits among 0 . . . 4) of length n and do not contain the string 00. Find a recurrence relation and give initial conditions for the ...
376 views

### How do I represent the set of all finite bit strings?

At first I thought I could just represent them with the set of natural numbers, because each bit string represents some natural number. However doing this would mean the strings '010' and '00010' are ...
185 views

### Bit representation and divisibility by 3

I was reading about how to know if a number is divisible by 3 given binary representation of the number. After googling a bit I read a statement and I am puzzled how is this correct. we have to ...
34 views

### Counting bit strings of length $70$ with two restrictions

There is a bit string of length $70$. At least one of the following restrictions must apply: i)The first $9$ bits cannot contain exactly $5$ 1s ii)The first $49$ bits cannot contain exactly $27$ ...
38 views

### Maximizing the number of occurrences of a fixed subsequence

Fix two positive integers $N$ and $M$ and assume $n:=\frac{N}{M}\in\mathbb{N}$. Consider a fixed binary sequence $Y=Y_1,\ldots,Y_M\in\{0,1\}^M$. The goal is to find an optimizing length-$N$ ($N\geq M$)...
### How many bitstrings of length $n = 10$ contain at least $k = 3$ consecutive 1’s? [duplicate]
I'm working on this problem and am having some difficulties. I know something important to keep in mind is that (as an example) $1110001111$ is just one bit string despite it having two individual ...