Questions tagged [bit-strings]
Use this tag for questions related to array data structures that compactly store bits.
1
vote
1answer
21 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
36 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
28 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
56 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
12 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
325 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
14 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
60 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
24 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
25 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
38 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
33 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
44 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
41 views
Enumeration of Binary Strings
Suppose we want to encode the natural numbers as bit strings as follows:
...
1
vote
1answer
37 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
44 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
38 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
44 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
23 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
66 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
163 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
46 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
69 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
67 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
61 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
53 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
84 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
164 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
22 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
80 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
174 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
74 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
32 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
37 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
42 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 ...
0
votes
0answers
25 views
12-bit Computer Discrete Math Conceptual Question pt. 2
Write an algorithm that takes a 12-bit, two’s complement integer k as its input, where k ≥ 0. Your algorithm must use the div and mod operators to count the number of 0-bits in k. For example, if k = ...
1
vote
1answer
55 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
60 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
117 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
54 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
746 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, ...
1
vote
2answers
71 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
1answer
38 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 $...
0
votes
2answers
217 views
Bitstring Mathematical Induction Proof
I have to use induction to prove that for any finite bitstring $s$, if $s$ ends in a $1$, then $01$ occurs at most one more time than $10$. Induct on the length of $s$.
I really can't solve this ...
1
vote
2answers
57 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
38 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 ...
