Questions tagged [bit-strings]

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

0
votes
0answers
29 views

Flipping k random bits to generate maximum number of 1 in any order.

We are provided with a series of numbers which contain only $1$ and $0$ and a number $k$. What is the maximum number of $1$ we can obtain by flipping any $k$ bits in any order any number of times. ...
1
vote
1answer
38 views

Number of binary words that can be formed

How many binary words of length $n$ are there with exactly $m$ 01 blocks? I tried by finding number of ways to fill $n-2m$ gaps with $0$ and $1$ such that no $'01'$...
0
votes
0answers
108 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
100 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
56 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
43 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 ...
2
votes
0answers
119 views

Multiplying strings as polynomials

Interdisciplinary Question: How to approach the question and arrive at the solution?
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 ...
2
votes
2answers
2k views

Bit flipping algorithm

The goal is to flip all the bits in the same direction (I mean all to be 1 ) For example, we have: 0110011 We need to flip the bits so that we get 1111111 We can only flip K consecutive bits at a ...
1
vote
1answer
33 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
43 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 ...
1
vote
4answers
547 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
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
65 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
23 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$ ...
0
votes
0answers
17 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
103 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
31 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
65 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
60 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
2answers
278 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 ...
0
votes
1answer
56 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
121 views

Enumeration of Binary Strings

Suppose we want to encode the natural numbers as bit strings as follows: ...
1
vote
1answer
51 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
92 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
27 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 ...
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=(...
1
vote
0answers
72 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 ...
0
votes
3answers
178 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
50 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
72 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
83 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
81 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
66 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 ...
-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
187 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
403 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
236 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^...
8
votes
2answers
133 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 ...