Questions tagged [bit-strings]
Use this tag for questions related to array data structures that compactly store bits.
3
votes
0answers
99 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 ...
0
votes
1answer
37 views
Proof of equivalence between two methods of binary to decimal conversion.
I have two binary to decimal conversion methods and want a proof - or an intuition at least - of why they are equivalent.
The first method is quite intuitive to me and seems to be more popular:
$[...
0
votes
2answers
51 views
How to prove there are unreachable states in this bit flipping algorithm only for lengths $n=3k+2$?
This is similar to Bit flipping algorithm, but the algorithm is a little different. Specifically, we have bit string of length $n$, and we can choose any bit to flip and then we flip also the two ...
1
vote
3answers
42 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 ...
0
votes
0answers
105 views
Characteristic Vector Question
I have been asked the following questions on a tutorial worksheet and am not sure how to answer.
"There is a natural relationship between sets and bit strings which is called the characteristic ...
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 ...
0
votes
1answer
35 views
Prove that for any three distinct positive integers, at least one will be greater than the xor of the other [closed]
That is, prove that for distinct positive integers $x$, $y$, and $z$, at least one of these integers will be greater than the bitwise XOR of the other two integers.
The only "progress" I managed to ...
1
vote
1answer
28 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
votes
1answer
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 ...
0
votes
1answer
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 = ?
1
vote
1answer
62 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 \...
0
votes
1answer
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$ ...
1
vote
4answers
483 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}...
0
votes
0answers
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 ...
0
votes
1answer
94 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 ...
0
votes
1answer
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 ...
-1
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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?
0
votes
1answer
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 ...
0
votes
3answers
107 views
Enumeration of Binary Strings
Suppose we want to encode the natural numbers as bit strings as follows:
...
1
vote
1answer
50 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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
3answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
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=(...
0
votes
3answers
174 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 ...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
81 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 ...
2
votes
2answers
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 ...
1
vote
0answers
62 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$...
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 ...
0
votes
2answers
262 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 ...
-1
votes
3answers
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 ...
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 ...
0
votes
1answer
179 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 ...
0
votes
1answer
380 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 ...
0
votes
3answers
191 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 ...
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
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$)...
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
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
3answers
77 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, <...
8
votes
2answers
130 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 ...
-1
votes
1answer
69 views
How many bit strings of length n are there with two or more consecutive zeros? [closed]
$a_n = 2^n - (a_{n-2} + a_{n-1})$
I have read this formula somewhere but don't know how its used
here $a_n$ is the number of bit-strings of length $n$
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 ...
0
votes
1answer
903 views
Computing the absolute value of a signed 32-bit two’s complement integer with bitwise operators
solution:
int iabs(int a) {
int t = a >> 31;
a = (a^t) - t;
return a;
}
Can someone explain at the math level why shifting 31 bits to the right, ...
