Skip to main content

Questions tagged [bit-strings]

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

Filter by
Sorted by
Tagged with
6 votes
2 answers
256 views

Counting bit strings with given numbers of higher-order bit flips

Background information Bit flips Given a bit string, we say that bit flip happens when $0$ changes to $1$ or $1$ changes to $0$. To find bit flips, we can shift the string by $1$ and xor that new ...
Valeriy Savchenko's user avatar
0 votes
0 answers
80 views

A question on binary strings and bit swapping.

I consider binary strings over the bit-alphabet $\{0,1\}$. A binary string $S$ is balanced if the number of occurrences in $S$ of the bit $0$ is the same as the number of occurrences of the bit $1$; $...
Nellina's user avatar
0 votes
1 answer
55 views

Reordering algorithm to fragment consecutive sequences of ones as much as possible

Recently, I came across the following problem: Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$. We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$. We call a &...
Thedby's user avatar
  • 1
2 votes
1 answer
153 views

Prove that $b_n = [x^n]\frac{1-x^2+x^3}{1-2x+x^2-x^3}$

A block of a $\{0,1\}$ -string is a maximal nonempty substring consisting only of $0$s or only of $1$s. Let $b_n$ be the number of $\{0, 1\}$ strings of length $n$ in which no block has length exactly ...
DrTokus1998's user avatar
0 votes
0 answers
58 views

Is my logic correct? A bit string of n with more 0s than 1s

I am learning about combinatorial and bit strings. I decided to use combinatorial reasoning and wanted to see if my logic made sense. The question: How many bit strings of length n contain more 0’s ...
coolcat's user avatar
  • 147
0 votes
0 answers
22 views

How many bit strings of length n contain more 0’s than 1’s? [duplicate]

To solve this, I think we need to use combinatorial reasoning.= Consider a bit string of length ( n ). There are ( 2^n ) possible bit strings of this length because each bit can independently be ...
coolcat's user avatar
  • 147
4 votes
1 answer
45 views

Average length of longest duplicated substring in a random binary string of length N

What is the average length of longest substring occurring at more than one position in a uniformly random binary string S of length N ? For example, ...
VainMan's user avatar
  • 1,735
0 votes
1 answer
63 views

Conceptual Question regarding Shannon Entropy and bits

It is said that the number of "information bits" contained in a certain piece of information can be roughly translated as the number of yes/no-questions that would have to be answered in ...
Xerxes123's user avatar
1 vote
1 answer
37 views

Recurrence for number of $L$-bit strings with no $0^{w}$

I have been trying and struggling to come up with a generalized recurrence relation for the number of $L$-bit strings with no runs of $w$ consecutive zeros. I have a relation that gives the right ...
filthywabbit's user avatar
0 votes
0 answers
21 views

Name for algorithm grouping carryless long division

When implementing multiplication in binary finite fields, Barrett reduction allows to perform division with two carryless multiplications and two XOR additions (and some one-time precomputation). ...
dragomang87's user avatar
0 votes
1 answer
27 views

Notation/operator for bit-length function

Defining the bit-length function over natural numbers as $BL(n) = \left\lceil \log_2(n+1) \right\rceil $ What are common notations for such bit-length function? It is frequently denoted as $|n|$ in ...
ibarrond's user avatar
  • 101
1 vote
1 answer
47 views

Help understanding the solution to this problem

Here is the problem: There are sixteen different ways of writing four-digit strings using 1s and Os. Three of these strings are 1010, 0100 and 1001. These three can be found as substrings of 101001. ...
mathisdagoat's user avatar
1 vote
2 answers
70 views

Number of bitstrings in a subset having Hamming distance $k$

Given a bitstring x and a subset $P \subset \{0,1\}^n $. There are $n \choose k $ bitstrings in $\{0,1\}^n $ with Hamming distance $k$. How many bistrings with Hamming distance $k$ are in the subset $...
user18722294's user avatar
0 votes
1 answer
78 views

How many bitstrings of length n contain 3 consecutive ones ("111")?

I tried creating a recurrence formula. Can someone evaluate it? a(n) =a(n-1)+2^(n-3)+a(n-3) 0-> followed by bitstring of length n-1 (represented by a(n-1)) 1->10->101; 1->10->100; 1->...
TheFire91's user avatar
2 votes
1 answer
119 views

What's the minimum guaranteed substring match between a binary string and a chosen rotation?

Given $n$: An adversary chooses a binary string $X$ of length $n$. I choose two distinct rotations of $X$, called $Y$ and $Z$, with the goal of maximizing $m$, the length of the longest prefix shared ...
kevincrawfordknight's user avatar
1 vote
1 answer
52 views

What are the mean and standard deviation of the convolution of two bit vectors?

I'm cryptanalyzing a cipher I've written, which takes a message of arbitrary size and returns a message of the same size. Because of the rotBitcount operation, ...
Pierre Abbat's user avatar
1 vote
0 answers
77 views

How can I calculate the orbit of a group action of a group generated by one element?

I have a bit string, $X$, of $n$ bits. I am applying an operation, $g$, which involves a permutation of the bits and then flipping the first $k$ bits. I have a proof that the $g$ generates a group ...
Jeff's user avatar
  • 873
0 votes
2 answers
42 views

Number of bitstrings of length 18 that have consecutive 1's — why is my solution wrong?

Consider bitstrings of the pattern 11....(16 dots). There are a total of 2^16 such bitstrings. Now consider the pattern 011.....(15 dots). It is clear that this pattern and the previous pattern don't ...
csmathhc's user avatar
  • 330
1 vote
1 answer
62 views

Entropy of a Random Variable - Sending Message about Outcome

Consider a random variable with probabilities taking on the values $1,2,\ldots,8$ with probabilities given by $$\left(\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{64}, \frac{1}{64}, \...
Iced Palmer's user avatar
0 votes
2 answers
46 views

The number of binary sequences of length 300 made up of 50 ones and 250 zeros so that between Every two ones has at least one zero.

I tried a scenario where the number 0 represents a red ball and the number 10 represents a blue ball. I have a collection of 200 red balls, each occupying one spot, and 50 blue balls, each occupying ...
barry's user avatar
  • 23
0 votes
1 answer
137 views

Expected value of the number of substrings 101 or 111 in the string

Let $X_1,X_2,...,X_n, n>6$ are independent, $P(X_i=0)=\frac{3}{4}$ or $P(X_i=1)=\frac{1}{4}$. Let $Y_n$ is the number of substring $101$ or $111$ in the string $(X_1,...,X_n)$. For example: for $(0,...
Miłosz 's user avatar
2 votes
0 answers
115 views

How to find the convex hull of the set $\left\{ {\bf x} \in \{0, 1 \}^n \mid {\bf 1}_n^\top {\bf x} = k \right\}$?

Given integers $k < n$, let $$ \mathcal{V} := \left\{ {\bf x} \in \{0, 1 \}^n \mid {\bf 1}_n^\top {\bf x} = k \right\} $$ Is it true that its convex hull is $\mathcal{S} := \left\{ {\bf x} \in[0,1]^...
Zang San's user avatar
0 votes
0 answers
51 views

number of n length binary strings not containing specific factor [SOLVED]. [duplicate]

EDIT: Thanks to RobPratt's insight, (https://oeis.org/A005251), I wrote a quick and dirty python program to generate the number of bin strings not containing a 3 length string; ...
noha's user avatar
  • 1
1 vote
0 answers
79 views

Longest common prefixes in a set of binary strings

Consider a set $D$ of $n$ uniformly random binary strings of length $m$. Fix $l \leq m$. We now sample an $m$-bit string uniformly at random from $\{0,1\}^m$. Let $\alpha$ be the $l$-bit prefix of ...
Jason Ptacek's user avatar
1 vote
1 answer
76 views

What is the intuition behind this recursive function?

The problem that I'm working on is: How many binary strings (strings with only 0 or 1) of length 10 are there such that there are no 3 consecutive ones and no 2 consecutive zeros? Let $a_n$ be the ...
py_math's user avatar
  • 302
0 votes
0 answers
58 views

Proving injectivity of a function that modifies binary strings

"$f : \{ 0, 1 \}^3 \rightarrow \{ 0, 1 \}^4$ is given by adding a copy of the first bit to the end of the binary string." An example would be $f(abc) = abca$, and I am asked to prove whether ...
KLG's user avatar
  • 11
11 votes
2 answers
249 views

Injection from binary strings with $i$ bits to $i+1$ bits

I want to find an injection $F$ from binary strings length $n$ with $i$ bits turned on to $i+1$ bits turned on, with the condition that if $F(S)=S'$, then $S'$ can be obtained from $S$ by simply ...
Confused Soul's user avatar
1 vote
0 answers
38 views

Maximal accuracy of logistic regression on the n-parity problem

Consider the standard logistic regression ('LR') function, $ y = \sigma(w^T \cdot x + b) $, where $\sigma$ is the logistic function ('sigmoid'). When checking the accuracy, we will consider the argmax ...
Ido4848's user avatar
  • 567
0 votes
1 answer
83 views

Binary strings using inclusion-exclusion

Let $U=\{0,1\}^{2n}$ and $A_i=\{x\in U: x_i=0 \land x_{i+1}=1\}$ for $1\le i\le 2n-1$. Let $J\in \mathcal{P}_r([2n-1])$ i.e subsets of $[2n-1]$ of cardinality $r$. What is the cardinality of $\cap_{j\...
SlyxBrd's user avatar
  • 527
3 votes
1 answer
85 views

Joining digits in binary string

Given a binary string of length $k \in \mathbb{N}_+$ find a maximum number of digits you can remove by combining adjacent elements into opposite ones (i.e you can combine 2 adjacent $1$s into $0$ or ...
Liam Brown's user avatar
0 votes
2 answers
102 views

Number of ways to split binary string?

Not answered, see my comments. Given a binary string like this: 1101 What's the number of possible ways to split it (where splitting the string doesn't necessary means having only 2 parts) For example:...
zoro's user avatar
  • 161
2 votes
1 answer
192 views

How to prove a bitstring structural induction problem

A bitstring is a string consisting of only 0s and 1s. Define “·” to be the operation of concatenation, and let $\epsilon$ be the empty bitstring. Consider the following recursive definition of the ...
someoneDumbb's user avatar
-4 votes
1 answer
56 views

the quantum world: is $f$ balanced or constant? [closed]

Why here on the page 15, the fact whether $f$ is constant or balanced is derived from the value of $f$ at $0$ only ?
user122424's user avatar
  • 3,936
1 vote
0 answers
16 views

Comparison of powers in the inequation of binary polynomials

In "2.3 Analysis" of Izu, Tetsuya et al. “Extending Bleichenbacher's Forgery Attack.” J. Inf. Process. 16 (2008): 122-129 there is a move, which should be obvious, but I keep struggling with ...
Sergey Kaunov's user avatar
0 votes
0 answers
43 views

Distinction 'limit to infinity' and 'inclusive infinity' for bitstrings

How to describe the difference: Take a digit string of countable infinite 0's and construct a collection of all such strings where we allow a 1 at any position with finitely preceding digits, or allow ...
Daniel Miedema's user avatar
1 vote
2 answers
138 views

Function to flip the bit of the $nth$ binary digit

In programming, every number is expressed in binary-- for example, the number $5$ is $101$. In this concept, we can "flip the bit" of a specific digit. For example, flipping 5's first digit ...
Andrew Baker's user avatar
0 votes
1 answer
76 views

Fast computation of $x^{1/p}$, where $x\in\mathbb{R}^+$ and $p=2^{n}$, where $n\in\mathbb{N}$ with bit shifts?

There is plenty of literature regarding the legendary Fast inverse square root routine from Quake, but can we do something similar to compute $x^{1/p}$ as given in the title? Given that $p$ is a power ...
Bobby's user avatar
  • 41
-1 votes
2 answers
383 views

How many bit strings exist of length ten or less, not counting the empty string?

My understanding is that for bit string of length $n$ there are $2^n$ bit strings. So the sum of all bit strings of lengths $1$ to $10$ would be $2^1$+$2^2$+ ... +$2^{10}$ = $2^{55}$. The empty ...
Accribus's user avatar
2 votes
1 answer
28 views

Convert an arbitrary string of bits to a 3D color such that strings with more bits in common have more similar colors

I am toying with a genetic algorithm for the first time to evolve a very simple neural network. For the purpose of rendering, I would like to assign my agents a color based on their 'genome', such ...
cebo's user avatar
  • 121
0 votes
1 answer
41 views

What is the reason in each of these subgroups of order $2^n$, each element's lower $n$ bits are distinct & form all possible $4$-bit patterns?

Let's take the example of the additive group $\Bbb Z/176\Bbb Z$ This has a subgroup of order $2^3$: $[0, 22, 44, 66, 88, 110, 132, 154]$ If you check the lower $3$ bits of each element in this ...
user93353's user avatar
  • 476
1 vote
1 answer
25 views

$a-b = (e + (a<<s)-(b<<s))>>s$, why it does not work for some $e$?

If I subtract 2 numbers shifted left to a number and shift right, I get the original number. Example: $$30 - 1 = ((30<<7) - (1<<7)) >> 7 = 29$$ or in other words $$a-b = ((a<<s)...
Rafaelo's user avatar
  • 103
1 vote
0 answers
37 views

Expected number of random bitstrings that match a certain prefix

I am faced with the following problem. Assume I generate $N$ random bitstrings of length $L$ without replacement, that is, no duplicate bitstrings are allowed. Now let $p$ be an arbitrary, but fixed, ...
dieter.ml's user avatar
  • 161
0 votes
1 answer
50 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. ...
juaninf's user avatar
  • 1,264
0 votes
0 answers
62 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?...
Ruma's user avatar
  • 11
2 votes
1 answer
119 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 ...
isaacg's user avatar
  • 957
0 votes
0 answers
35 views

Bitstring counting with three elements

A bitstring (length $10$ $\{0,1\}$) has exactly $120$ string that contains three $0$s, but now I am trying to find out how many strings with three zeroes if the string looks like this: $\{0,1,\phi\}$. ...
victorialangoe's user avatar
1 vote
1 answer
82 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-\{\...
Jackson Walters's user avatar
1 vote
0 answers
119 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: ...
No Name's user avatar
  • 145
0 votes
0 answers
395 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 ...
Gautham J's user avatar
1 vote
1 answer
1k 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 ...
Riley Varga's user avatar