Questions tagged [bit-strings]

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

92 questions
29 views

Flipping k random bits to generate maximum number of 1 in any order.

We are provided with a series of numbers which contain only $1$ and $0$ and a number $k$. What is the maximum number of $1$ we can obtain by flipping any $k$ bits in any order any number of times. ...
38 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'$...
100 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

43 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 ...
29 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 = ?
65 views

17 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 ...
103 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 ...
31 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 ...
65 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 ...
60 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?
56 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 ...
121 views

Enumeration of Binary Strings

Suppose we want to encode the natural numbers as bit strings as follows: ...
51 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 ...
92 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 ...
27 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 ...
72 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 ...
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=(...
178 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 ...
50 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 ...
72 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 ...
83 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 ...
81 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 ...
66 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$...
96 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 ...
278 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 ...
43 views

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 ...
187 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 ...
403 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 ...
236 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 ...