Questions tagged [bit-strings]
Use this tag for questions related to array data structures that compactly store bits.
156
questions
0
votes
1
answer
33
views
At most $k$ contiguous $\mbox{true}$ values in a Boolean array using SAT
Given an integer $k > 0$ and a Boolean array $A$ of length $n$, find a simplified and efficient CNF formula to ensure that there is not more than $k$ contiguous $\mbox{true}$ values in this array. ...
- 1,242
0
votes
0
answers
21
views
How many n-bit strings are unbalanced?
I am stuck on this question that i came across in my assignment. What does it mean by unbalanced string? I don't know the proper approach of solving this question
How many n-bit strings are unbalanced?...
- 11
2
votes
1
answer
42
views
Unique-xor sets
Let a set $S$ of nonnegative integers be a "unique-xor" set if all pairs of distinct integers in $S$ have different bitwise xor from all other pairs.
Let $x(n)$ be the least maximum element ...
- 645
0
votes
0
answers
19
views
Bitstring counting with three elements
A bitstring (lenght 10 {0,1}) has exactly 120 string that contains three 0s, but now I am trying to find out how many strings with tree zeros if the string looks like this: {0,1,φ}. Can I still use ...
0
votes
0
answers
51
views
Is standard deviation an associative operation? How does this affect the use of a combiner?
The mean µ of a set of numbers X = {x1, x2 ... , xn} is defined as:
enter image description here
The standard deviation σ of a set on numbers X is defined as:
enter image description here
1
vote
1
answer
78
views
Why is $\lim_{b \rightarrow 1} concat_b(x,y) \ne x+y$ for base-$b$?
Let $x=x_N\ldots x_0$, $y=y_M\ldots y_0$ be integers with base-$b$ digits $0 \le x_i,y_j < b$. Concatenate them via
$$x \otimes_b y\triangleq x_N\ldots x_0 y_M\ldots y_0=b^{len_b(y)}x+y=b^{1-\{\...
- 1,315
1
vote
0
answers
27
views
Find the XOR of every other number in a given range
Lets say that R=15 and L=8, then how can I efficiently find:
15 XOR 13 XOR 11 XOR 9
If R=20 and L=10, then it would be:
...
0
votes
0
answers
50
views
How do we add multiple binary bits with carry using boolean operators XOR and AND.
My question is similar to How do I add multiple binary numbers without using a partial sum?.
For example, if we add two bits, a and b, then sum bit = a XOR b and carry bit = a AND b.
Is there a way to ...
1
vote
1
answer
98
views
Why does bitshifting to the right work as division?
So I'm trying to understand why bitshifting integers to the right works as division.
Take the number 4200. If I shift it to the right by 1, it divides by 2.
If I ...
- 113
1
vote
1
answer
50
views
Does the Prouhet-Thue-Morse sequence eventually contain its bitwise boolean complement in whole?
My intuition says that it does not, but I am struggling to prove it. It definitely contains any finite consecutive subsequence ("substring") of the latter, by its construction. I also ...
- 766
0
votes
0
answers
37
views
Generating restricted finite additive $2$-bases from doubly-eager bit-strings
A bit-string is any finite sequence of $1$s and $0$s. For example, $1011011$, $1011010$, and $000110$ are bit-strings.
In this post, I will refer to bit-strings as strings, to be concise.
I now ...
- 103
2
votes
0
answers
46
views
Generalized expected Hamming distance
Let $x,y\in\{0,1\}^n$ be uniformly drawn at random from the set of all length-$n$ bitstrings $\{0,1\}^n$. Let $d(x,y)$ be the Hamming distance of two such bitstrings, i.e. the number of positions at ...
- 419
0
votes
1
answer
2k
views
Determine whether f is a function from the set of all bit strings to the set of integers.
Qustion: Determine whether f is a function from the set of all bit strings to the set of integers if
(a) f(S) is the position of a 0 bit in S.
(b) f(S) is the number of 1 bits in S.
(c) f(S) is the ...
- 55
0
votes
1
answer
90
views
Finding the Number of $1$ in a Binary String
Is there a general formula/ recurrence relation for finding the number $N$ of $1$ in an $n$ binary string representation of an integer $I$ ?
For the simplest case where $I\mod{2^n}=0$, it is easily ...
- 1,090
0
votes
1
answer
69
views
Proof: Any integer number is a binary substring of some prime
Does there exist a (dis)proof of the following proposition:
For any positive integer N, there exists a prime P with
larger number of significant bits than that of N, and N is a binary
substring of P.
...
- 19
1
vote
0
answers
57
views
Binary Representation of 3 to some Power of 2
I believe the following is a well-known result.
The lowest ($i+3$) bits in the binary representation of $3^{2^i}$ ($i>0$) has the form "$10..01$", namely, all bits are zeros except the ...
- 123
3
votes
0
answers
155
views
Mathematical equivalents of bitwise AND, OR, and XOR operators
$\hphantom{bullet}$I've been looking at encryption and hashing and was wondering if there was a way to put bitwise operations into a more math based form. After a little research and a lot of thinking,...
- 31
1
vote
2
answers
45
views
How to check if an integer can be represented with all set bits for any given base?
By all set bits, I mean all the set bits are placed consecutively together. e.g., for base 2, we have 1, 3, 7, 15, 31, 63, i.e., any integer $x$ such that $x = 2^m - 1$ for some integer $m$.
In binary,...
- 1,280
0
votes
0
answers
48
views
Problem by transforming an equation
I am currently working on a task and I have a problem doing the next step:
Given a function $f:\{0,1\}^n\to\{0,1\}^n$, such that for each distinct $x\in\{0,1\}^n$ the output $f(x)$ is unique, except ...
0
votes
0
answers
49
views
Calculating magic formulas of bitwise operations
From here, https://codeforces.com/contest/424/problem/C. The solution was given here, but it is hard to understand, https://codeforces.com/blog/entry/11944
Imagine you are given a sequence of ...
- 4,862
1
vote
1
answer
77
views
Probability that $010$ is present in an $n$-length binary sequence
Imagine a memoryless source that outputs 0's and 1's with probabilities $P_X(0)$ and $P_X(1)$. For example, $P_{X^2}(00)=P_X(0)P_X(0)$.
How would you calculate the probability that the sequence $010$ ...
- 341
0
votes
0
answers
41
views
Expected Number of Bit Chunks
We begin with a string of zeros of length K > 1. We perform N random "flips" by choosing an index from 1 to K uniformly at random and flipping the bits from that index through index K, e....
- 21
0
votes
1
answer
56
views
The probability that $0$ occurs exactly twice in $x^n$
Consider a binary random variable $X$ taking value over $\mathcal{X} = \{0,1\}$ with probabilities $P_X(1)=aP_X(0)$ (with $a>0$) and an i.i.d. sequence of length $n$ denoted by $x^n = (x_1,...,x_n)$...
- 341
2
votes
0
answers
36
views
Lower bound on the probability that a string has a fixed substring
Let us suppose we have a fixed bit string P of length $n$. We have to prove that there is a constant $k>0$, such that for any $n$, if we uniformly randomly generate a bit string $Q$ of length $k\...
- 21
4
votes
1
answer
87
views
Substring of a bit string probability [closed]
Given a fixed bit string $A$ of length $k$ and a randomly generated bit string $B$ of length $n > k$, meaning each bit of $B$ has probability $1/2$ to be zero or one respectively, how can one ...
- 435
0
votes
1
answer
46
views
Hamming distance between consecutive primes
The Hamming distance between strings of equal length is the number of mismatches between the strings
MYSTERY
MASTERS
^ ^
This distance can be defined for ...
- 13.3k
5
votes
2
answers
382
views
Bit strings and probability
Given a bit string of length $n$, I should develop a probabilistic algorithm that answers one of the following questions:
Does the bit string have more zeros than ones?
Does the bit string have more ...
- 313
1
vote
0
answers
41
views
Find a sum of all numbers in the list which have zero in the high-order digit.
Let's fix a positive integer number $p$.
Let $x$ be a non-negative integer that can be expressed using binary system in such a way: $x=\overline{x_{p-1},...,x_0}$, where $x_0,...,x_{p-1}\in \{0,1\}$. ...
- 173
-1
votes
1
answer
76
views
How many bit strings that begin with 1 and contain two consecutive 1s [closed]
Find a recurrence relation for the number of bit strings of length n that contain two consecutive 1s and start with 1? The answer in my book is $a_{n} = a_{n-1} + a_{n-2} + 2^{(n-3)}$, however I am ...
0
votes
1
answer
77
views
Correct set notation regarding bit strings
Let's say we have:
\begin{align*}
\mathcal{A} &= \{0000,0101,0011,0010\}\\
\mathcal{B} &= \{1100,1001\}\\
\mathcal{R} &= \{0011,0010\}
\end{align*}
Using set notations, how do I express ...
- 71
0
votes
0
answers
43
views
Representing a Number as the Sum of Powers of Form $k^k$.
So I was wondering if it would be useful to instead of writing a number in base $2$ or $3$, we use functions in general as bases. So like writing it as the sum of squares or other increasing functions....
- 53
0
votes
1
answer
43
views
In classical computing, what is meant by a bit string function?
What is exactly meant by this function? I haven't found any clarification how exactly this function works:
$$f: \{0,1\}^n \rightarrow \{0,1\}^m$$
So it takes a n-bit string and turns it into an m-bit ...
- 109
3
votes
3
answers
217
views
How many length-$n$ bitstrings containing $3$ consecutive $0$s and $4$ consecutive $1$s are there?
How many length-$n$ bitstrings containing $3$ consecutive $0$s and $4$ consecutive $1$s are there?
I thought that $a_n$ can be constructed in three ways:
The strings that contain both three ...
user898368
1
vote
0
answers
35
views
Combinatorics on subgraphs of the Hamming cube
Let $d \in \mathbb{N}$ even, and let's consider the bipartite graph $G_d$ that has nodes labeled on the left side by $\{x \in \{0,1\}^d : |x| = d/2\}$ and on the right side by $\{x \in \{0,1\}^d : |x| ...
- 598
1
vote
0
answers
32
views
Binary strings containing every $SS$
Let $k$ be a positive integer. Prove that a binary string (of $0$'s and $1$'s) which contains all strings of the form $SS$, where $S$ is a binary string of length $k$, has length at least $2^{k+1} + k ...
- 2,547
0
votes
1
answer
63
views
Combinatorics w/ binary string
How many string of 16 bit can we build having the following constraints:
There must be exactly 5 one
Between two 1 there must be at least two 0.
Example of valid string:
(1) 1 00 1 00 1 00 1 00 1 ...
- 55
0
votes
1
answer
37
views
convergence sequence of xor bit operation
Given positive integer $m$, we consider the integers up to $m$ bits.
Let $mask = 2^m - 1$ and consider sequence, $a_0 = 0, a_1 = 1$,
For $i \ge 2$,
$$a_i = (a_{i-2}) \oplus (a_{i-1}) \oplus (a_{i-1}&...
- 303
1
vote
0
answers
82
views
How to optimize subset sum problem through bitmask with the option to generate indices?
I was solving the subset-sum problem. There are many ways to solve the problem but I prefer the bitmask approach which is explained here.
Now If I want to get the index of the elements that form my ...
- 71
0
votes
0
answers
57
views
How many different ways a string of '$n$' length can be divided into '$r$' number of non-overlapping non-empty segments?
I was trying to figure out some computation regarding string operations. Suppose, I have a string of length $n$ and I want to split the string into $m$ number of non-overlapping segments. How many ...
- 3
1
vote
0
answers
31
views
Semigroup of bit-string substitutions - any pointers?
Consider a pair $s=(s_0,s_1)$ of bit-strings (strings of 0s and 1s). Let $s$ act on a bit-string $b$ by replacing every $0$ in $b$ by $s_0$ and every $1$ in $b$ by $s_1$. Then the set $S$ of all such '...
- 11
5
votes
3
answers
1k
views
Let $b_{n}$ denote the number of compositions of $n$ into $k$ parts, where each part is one or two. Find the generating series for $b_{n}$
I am stuck with this combinatorics problems -
Let $n$ be a positive integer and let $b_{n}$ denote the number of compositions of $n$ into $k$ parts, where each part is one or two. For example, $(1, 2, ...
- 83
-2
votes
2
answers
39
views
Determining Big O Method
The image attached contains a sorting problem and its solution. I'm having a hard time understanding the very last bullet point of the solution in determining Big O.
Why do we need to compare as well ...
1
vote
1
answer
59
views
What would the notation for this binary string look like?
Every block of 1's of length $\ge 4$ cannot be followed by a block of 0's of length $\ge 4$, and any block of 1s of length 1, 2 or 3 must be followed by a block of 0s whose length is congruent to 1 ...
1
vote
0
answers
65
views
A de Bruijn sequence of infinite length?
A de Bruijn sequence is a (typically) binary string of length $2^k$ which contains every binary string of length $k$ as a substring exactly once, if you allow it to wrap around. For example, ...
- 4,941
0
votes
0
answers
23
views
What am I missing here? Basic Bit Operation
Consider the bit strings $A=001100$ and $B=010101$ then $A\vee B`= ? $ ($B`=$bitwise NOT)
First I wrote $B`$ and get,
$$B`= 101010$$
then I took first "$0$" of $A$ and "$1$" of $B`$ then get (1), ...
- 11
0
votes
1
answer
49
views
Boolean expression for a problem
I want to express problems like this in boolean expression with say $XOR$, or operations etc.
$HD$ = Hamming distance
Say for $HD(2^4, 0000)\geq2\;$ the boolean expression is $$x1 (x2+x3+x4) + x2 (...
- 11
0
votes
1
answer
57
views
What's this compression technique called?
Consider this string of 1's, 0's (spaces added for readability):
1010 1010 1010 1010
We can ...
- 476
0
votes
1
answer
35
views
Why does this Boolean formula $F$ always evaluate to zero given input $x'$?
Let $\oplus$ mean the exclusive OR operator, I have this boolean formula $F$ which takes inputs $x$, where given $|x|=n$, we have:
$$x:\{a_1,a_2,a_3,...,a_{n/2},b_1,b_2,b_3,...,b_{n/2}\}$$
and the $...
- 705
3
votes
2
answers
45
views
Finding the number of bit sequences without using recursion
How many 8-bit strings without three consecutive 1's are there that start with 1?
I used recursion and found that the answer is 68, but this was asked in a high school test so I am looking for an ...
- 459
0
votes
0
answers
74
views
Maximize the entropy of Hamming distance
We have a set of possible "key"s represented by bitstrings of length $k$. For example, when $k=3$, it can be $S = \{001, 010, 011, 000, 111\}$. I would like to find a "guess", which maximizes the ...
- 666