Questions tagged [bit-strings]

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

Filter by
Sorted by
Tagged with
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. ...
user avatar
  • 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?...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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
user avatar
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-\{\...
user avatar
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: ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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,...
user avatar
  • 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,...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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....
user avatar
  • 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)$...
user avatar
  • 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\...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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\}$. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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....
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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| ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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}&...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 '...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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), ...
user avatar
  • 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 (...
user avatar
  • 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 ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 666