Questions tagged [bit-strings]

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

10
votes
1answer
636 views

Counting Binary Strings (No block decompositions)

The main question goes : How many binary strings of length $n$ are there that do not contain an odd string of $0$'s as a maximal substring? (So $1001$ is okay but $10001$ is not) A maximal ...
9
votes
3answers
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=(...
8
votes
2answers
133 views

What is the least prime which has 32 1-bits?

On the many prime number investigation sites across the web I haven't been able to find the answer. Also my math isn't good enough to compute it from first principles. So, what is the least prime ...
6
votes
2answers
248 views

Count number of exact matching sequences

Consider all pairs of binary strings $P$ and $T$. Let the length of $P$ be $n$ and the length of $T$ be $2n-1$. For each such pair, we can check if $P$ is exactly equal to each of the $n$ substrings ...
5
votes
4answers
345 views

Number of q-ary strings of length m which do not contain k consecutive zeros

A finite q-ary-alphabet is given $$A_q = {0,1,2,...,q-1}.$$ Now I am considering the set of all finite strings over the alphabet $A_q$. I am interested on the number $$N(m,k)_{A_q}$$ of strings of ...
4
votes
2answers
569 views

What is the number of binary strings of length N with exactly R runs of ones, with C total ones?

I'm concerned with the total number of ones, and the total number of runs, but not with the size of any of the runs. For example, $N=8$, $R=3$, $C=5$ includes 11101010, 01101011 among the 24 total ...
4
votes
2answers
368 views

Number of binary and constant-weight strings of length m which do not contain k consecutive zeros

I am considering the set of all finite and binary strings. In the following I am interested on the number $N(m,k,r)$ of strings with length $m$ and Hamming weight $r$ which do not contain $k$ ...
4
votes
1answer
58 views

Shortest universal bit string: One string to contain all others

Let $s$ be a string of bits. Treat it as a cycle, with the first bit following the last. Say that $s$ is universal for $n$ if all the $2^n$ strings of $n$ bits can be found in $s$ as consecutive, left-...
3
votes
5answers
137 views

Notation for the set $\{0,1\}$

When doing some complexity theory, I get bored of typing all the time the set $\{0,1\}$. Is there some widely used alternate fancy notation?
3
votes
1answer
119 views

Does there exist an infinite set of binary strings $S$ such that no element of $S$ contains any other element of $S$ as a proper substring.

A binary string $a$ (of length $n\geq0$) is a finite sequence $(a_1,\ldots,a_n)$, with $a_i\in\{0,1\}$. We write this as $a=a_1\cdots a_n$. If the length is zero we write the binary string as $\...
3
votes
3answers
640 views

How many binary strings (with a given number of occurrences of 0 and 1) are there that do not contain a given substring?

I know my binary string is composed of exactly $n$ $1$s and $m$ $0$s. How many such strings are possible, if we add the constraint that they must not contain a specific given substring $S$ (whose ...
3
votes
0answers
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 ...
3
votes
0answers
23 views

Is reversing a string an example of a one to one function?

The word "apple" reversed yields "elppa". No other input can produce the same output. And in such a scenario can palindromes also be included in the list of permissible strings. Was wondering about ...
2
votes
2answers
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 ...
2
votes
4answers
1k views

Find a recurrence relation for the number of bit strings of length n that do not contain “0011”

So this is what I thought: i) start with 1: $f(n-1)$ ii)start with 01: $f(n-2)$ iii) start with 000 : $f(n-3)$ iv) start with 0010: $f(n-4)$ Though I was told it's not true. I would like to know ...
2
votes
2answers
2k views

Bit flipping algorithm

The goal is to flip all the bits in the same direction (I mean all to be 1 ) For example, we have: 0110011 We need to flip the bits so that we get 1111111 We can only flip K consecutive bits at a ...
2
votes
1answer
90 views

Estimate asymptotic behaviour by looking on ordinary generating function

I am interested on the asymptotic behaviour ($m \rightarrow \infty$) of the number of $q$-ary strings of length $m$, which do not contain $k$ consecutive zeros. The link Number of q-ary strings of ...
2
votes
1answer
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 ...
2
votes
1answer
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$ ...
2
votes
2answers
80 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 ...
2
votes
1answer
71 views

Any discernible pattern between two strings that are each XOR'd against a common string?

Given: three random strings that are of the same length - A, B, C RB = A xor B RC = A xor C Are there any discernible bit-string patterns to be found between the ...
2
votes
1answer
528 views

How to find the distinct equivalence classes for the set of all bit strings of length 5

Let B denote the set of all bit strings of length 5, $b_1,b_2,b_3,b_4,b_5$. Define a relation R on B by: two bit strings are related by R if and only if they both have bits $b_1$ the same and both ...
2
votes
0answers
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$)...
2
votes
0answers
118 views

Multiplying strings as polynomials

Interdisciplinary Question: How to approach the question and arrive at the solution?
1
vote
4answers
537 views

Finding numbers by given XOR values.

Given XOR values of 3 indices how can we find the numbers? Like say if I have indices from 1 to 7, how can I find the numbers by given XOR values? I have: $X_{1} \oplus X_{3} \oplus X_{5}=V_1$ $X_{1}...
1
vote
2answers
93 views

Loop over bit permutation one flip at a time

A bitstring is defined by a sequence of ones and zeros, e.g. "0101110111". Equivalently, it is defined by an integer as its binary representation. I want to calculate a certain function of a ...
1
vote
3answers
888 views

How many bit strings contain exactly eight $0\,s$ and ten $1\,s$ if every $0$ must be immediately followed by a $1$

Question How many bit strings contain exactly eight $0\,s$ and ten $1\,s$ if every $0$ must be immediately followed by a $1$ I know a question is already posted here, but i am getting doubt in my ...
1
vote
1answer
132 views

Minimum number of bit-flips to enumerate all bit-strings

If you have an $n$-bit binary string initialised in $000...000$, and at each step you are allowed to flip a single bit, what is the minimum number of flips required to have arrived at every possible $...
1
vote
1answer
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 ...
1
vote
1answer
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'$...
1
vote
1answer
65 views

How to shift right in modular arithmetic $2^n$ using only subtraction and multiplication.

In modular arithmetic $2^n$ it is easy to shift left number $x$ by doing $(x\ll 1)=2x=x+x=x-(0-x)$. Shifting right on the other hand is integer division by the power of 2, e.g. $(x\gg 1)=\lfloor x/2 \...
1
vote
2answers
59 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?
1
vote
3answers
80 views

Expected number and probability of a series of 1s in a bit string.

Suppose the sequence 1001111011011 has a total of $4$ "blocks" of one, because number of contiguous sequences made of ones (1, <...
1
vote
1answer
33 views

Given $N$ slots and $S$ objects to fill those slots, how many ways are there to fill the slots such that no two objects are adjacent.

Given $N$ slots and $S$ objects to fill those slots, how many ways are there to fill the slots such that no two objects are adjacent? I can't see a general pattern for this. If I take $N=7$ and $S = ...
1
vote
1answer
56 views

counting set bits of a natural number

For a natural number $n$ let $f(n)$ denote the number of set bits of $n$ - which is basically the Hamming weight of the binary representation of $n$. See wiki for more info. I have to prove that $f(n^...
1
vote
2answers
2k views

How to find the least significant bit position using bit position common to two numbers?

Let's say, I have two numbers $$a = (01110100)_2$$ and $$b = (01101011)_2$$ How to find the position of the least significant bit common to a and ...
1
vote
1answer
37 views

Prove that the number of bits in a positive $m$-bit integer $n$ is $n-\sum_{k=1}^{m-1} \lfloor n/2^k \rfloor$

I just read this result: The number of bits in a positive $m$-bit integer $n$ is $n-\sum_{k=1}^{m-1} \lfloor n/2^k \rfloor$. The proof is just outlined, and I thought that it would be interesting to ...
1
vote
3answers
43 views

Summation formula for this?

I have found the following summation formula based on a recurrence. It supposes $n = 2^k$ where k is an integer. I've intuitively discovered that the following closed form may be true (following the ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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$...
1
vote
0answers
56 views

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 ...
1
vote
0answers
53 views

What is the graph of my chances to mine a bitcoin?

Consider the next hashing definishion of $f(x)$ $$f(1) = 100$$ $$f(x) = \operatorname{SHA-256}(f(x-1))$$ Where $x$ is a positive integer and SHA-256 is the hash algorithm. You can think of SHA-256 ...
1
vote
1answer
40 views

Number of Ternary sequences least one $2$ appears to the left of a $0$

Find a recurrence for $a_n$, the number of ternary sequences of length $n$ in which at least one $2$ appears to the left of a $0$. I am not sure how to think of this. If you start with a $0, 1$ or $...
1
vote
2answers
58 views

Probability a bit in a bit string is 1 after swapping [duplicate]

Stuck on a homework question, so I could use all the help I could get. Let $x = x(1), \dots , x(n)$ be a bit string containing exactly $m$ occurrences of 1. Consider the following operation on $x$: ...
1
vote
1answer
49 views

Bit swapping probability question

Let $x = x(1), \dots , x(n)$ be a bit string containing exactly $m$ occurrences of 1. Consider the following operation on $x$: we choose a random pair of indices $(i,j),$ and we swap $x(i)$ and $x(j)$ ...
1
vote
0answers
47 views

Probability that two bit sequences match more than 60%

Assume that there is a random bit sequence generator that each time returns a bit sequence of length 100. Each bit of the sequence can be a 1 or 0 with equal probability. Question: What is the ...
1
vote
0answers
47 views

Number of bin. strings with Hamming weight r, which do not contain k consecutive zeros for large string length

I am interested in the number of binary strings of length $m$ and Hamming weight $r$, which do not contain $k$ consecutive zeros. A nice derivation of that number is in Number of binary and constant-...
1
vote
1answer
140 views

Question about equivalence relation/bitstring

Actually i have no idea about this question.i know the definition of equivalence relations 1-) reflective 2-) symmetric 3-) transitive but not more :(