Questions tagged [bit-strings]

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

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
944 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
94 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
40 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
237 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
58 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
47 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 ...
1
vote
3answers
890 views

How many bit strings contain exactly eight $0\,s$ and ten $1\,s$ if every $0$ must be immediately followed by a $1$

Question How many bit strings contain exactly eight $0\,s$ and ten $1\,s$ if every $0$ must be immediately followed by a $1$ I know a question is already posted here, but i am getting doubt in my ...
2
votes
1answer
528 views

How to find the distinct equivalence classes for the set of all bit strings of length 5

Let B denote the set of all bit strings of length 5, $b_1,b_2,b_3,b_4,b_5$. Define a relation R on B by: two bit strings are related by R if and only if they both have bits $b_1$ the same and both ...
4
votes
2answers
571 views

What is the number of binary strings of length N with exactly R runs of ones, with C total ones?

I'm concerned with the total number of ones, and the total number of runs, but not with the size of any of the runs. For example, $N=8$, $R=3$, $C=5$ includes 11101010, 01101011 among the 24 total ...
0
votes
0answers
333 views

Number of binary strings of length n where specific substrings occur more than m times in total

Problem Given integers $n,m,k,v$ count the number of possible bit strings $s$ of length $n$ such that at least $m$ of the contiguous substrings of $s$ of length $k$ have value greater than $v$ when ...
1
vote
2answers
2k views

How to find the least significant bit position using bit position common to two numbers?

Let's say, I have two numbers $$a = (01110100)_2$$ and $$b = (01101011)_2$$ How to find the position of the least significant bit common to a and ...
2
votes
1answer
90 views

Estimate asymptotic behaviour by looking on ordinary generating function

I am interested on the asymptotic behaviour ($m \rightarrow \infty$) of the number of $q$-ary strings of length $m$, which do not contain $k$ consecutive zeros. The link Number of q-ary strings of ...
1
vote
0answers
47 views

Number of bin. strings with Hamming weight r, which do not contain k consecutive zeros for large string length

I am interested in the number of binary strings of length $m$ and Hamming weight $r$, which do not contain $k$ consecutive zeros. A nice derivation of that number is in Number of binary and constant-...
0
votes
0answers
29 views

Asymptotic Behaviour of a formula

I have the following hideous equation $$ \frac{1}{n} \log_q (q^lx) $$ with \begin{equation} x=\sum_{i=0}^{\lfloor \frac{n}{l} \rfloor -1} \left( \sum_{j=0}^{\lfloor \frac{n-(i+1)l}{l} \rfloor} (1-q)^j ...
3
votes
1answer
119 views

Does there exist an infinite set of binary strings $S$ such that no element of $S$ contains any other element of $S$ as a proper substring.

A binary string $a$ (of length $n\geq0$) is a finite sequence $(a_1,\ldots,a_n)$, with $a_i\in\{0,1\}$. We write this as $a=a_1\cdots a_n$. If the length is zero we write the binary string as $\...
2
votes
1answer
71 views

Any discernible pattern between two strings that are each XOR'd against a common string?

Given: three random strings that are of the same length - A, B, C RB = A xor B RC = A xor C Are there any discernible bit-string patterns to be found between the ...
0
votes
1answer
303 views

Combinations and Bit String help

I have a 15 bit string, and I want to find how many combinations there are where there are no consecutive two 0's in a row. If I'm interpreting this right, combinations of 001001001001001 and ...
4
votes
2answers
369 views

Number of binary and constant-weight strings of length m which do not contain k consecutive zeros

I am considering the set of all finite and binary strings. In the following I am interested on the number $N(m,k,r)$ of strings with length $m$ and Hamming weight $r$ which do not contain $k$ ...
0
votes
2answers
223 views

bit strings recurrence

Let $f(n)$ denote the number of bit strings. (Words from the alphabet $\{0,1\}$) of length $n$ which do not contain three consecutive zeros. How would you write a linear recurrence of order 3 with ...
1
vote
1answer
140 views

Question about equivalence relation/bitstring

Actually i have no idea about this question.i know the definition of equivalence relations 1-) reflective 2-) symmetric 3-) transitive but not more :(
2
votes
4answers
1k views

Find a recurrence relation for the number of bit strings of length n that do not contain “0011”

So this is what I thought: i) start with 1: $f(n-1)$ ii)start with 01: $f(n-2)$ iii) start with 000 : $f(n-3)$ iv) start with 0010: $f(n-4)$ Though I was told it's not true. I would like to know ...
1
vote
1answer
132 views

Minimum number of bit-flips to enumerate all bit-strings

If you have an $n$-bit binary string initialised in $000...000$, and at each step you are allowed to flip a single bit, what is the minimum number of flips required to have arrived at every possible $...
4
votes
1answer
58 views

Shortest universal bit string: One string to contain all others

Let $s$ be a string of bits. Treat it as a cycle, with the first bit following the last. Say that $s$ is universal for $n$ if all the $2^n$ strings of $n$ bits can be found in $s$ as consecutive, left-...
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 ...
10
votes
1answer
637 views

Counting Binary Strings (No block decompositions)

The main question goes : How many binary strings of length $n$ are there that do not contain an odd string of $0$'s as a maximal substring? (So $1001$ is okay but $10001$ is not) A maximal ...
0
votes
0answers
116 views

Propositional logic as sets of bit-vectors

Consider that formulas in propositional logical can be represented as sets of bit-vectors. For example, a formula $\neg b$ (all bit-vectors of the type $?0?$) with three atomic propositions $a,b$ and $...
5
votes
4answers
345 views

Number of q-ary strings of length m which do not contain k consecutive zeros

A finite q-ary-alphabet is given $$A_q = {0,1,2,...,q-1}.$$ Now I am considering the set of all finite strings over the alphabet $A_q$. I am interested on the number $$N(m,k)_{A_q}$$ of strings of ...
0
votes
0answers
43 views

Deduce patterns of divisibility in bit strings

This is partially a computer science question, but belongs here as well. The question has to do with the bit representation of integers. For simplicity, assume only non-negative integers. Can we find ...
6
votes
2answers
248 views

Count number of exact matching sequences

Consider all pairs of binary strings $P$ and $T$. Let the length of $P$ be $n$ and the length of $T$ be $2n-1$. For each such pair, we can check if $P$ is exactly equal to each of the $n$ substrings ...
2
votes
0answers
119 views

Multiplying strings as polynomials

Interdisciplinary Question: How to approach the question and arrive at the solution?
0
votes
1answer
251 views

Bit string functions

I'm enrolled in a course of ML, and we were asked to provide a problem domain for a fitness functions over bit string where we have to find the value of X which maximize the output of the function. ...
3
votes
5answers
138 views

Notation for the set $\{0,1\}$

When doing some complexity theory, I get bored of typing all the time the set $\{0,1\}$. Is there some widely used alternate fancy notation?
1
vote
1answer
38 views

Prove that the number of bits in a positive $m$-bit integer $n$ is $n-\sum_{k=1}^{m-1} \lfloor n/2^k \rfloor$

I just read this result: The number of bits in a positive $m$-bit integer $n$ is $n-\sum_{k=1}^{m-1} \lfloor n/2^k \rfloor$. The proof is just outlined, and I thought that it would be interesting to ...
0
votes
1answer
53 views

What will be the value of least significant byte?

Let N be the sum of all numbers from 1 to 1023 except the five prime numbers 2, 3, 11, 17 , 31, all numbers are represented by two bytes, what is the value of least significant byte? My approach is ...
0
votes
1answer
33 views

The average length of strings in finite free set

A finite set $S$ of binary strings is called free if no string is a prefix of other string in $S$. I need to show that the average length of string in $S$ is at least $\log n$, where $n$ is the number ...
0
votes
0answers
618 views

Given binary string of length n with k bit sets, how many permutations have x consecutive ones and no y consecutive ones where y > x

Not sure if this is possible to calculate in an easy way but given binary string of length n with k bit sets, how many permutations have x consecutive ones and no y consecutive ones where y > x An ...
0
votes
1answer
44 views

How many bit-strings can be formed with ones and zeros?*

How many bit-strings can be formed with 6 ones and 28 zeros if each line must start with 1 and after each one must be at least three 0? Sombebody please help!
0
votes
1answer
45 views

Show that for any n ≥ 1, there is an error-detecting set of strings of length n, using the digits 0, 1, and 2, that has 3n−1 strings?

Can anyone please show me a proof by induction for this? A set of error-detecting strings is a set of strings that differ by more than one character. For example: for {0,1,2} for n = 2: {00,11,22} ...
3
votes
3answers
650 views

How many binary strings (with a given number of occurrences of 0 and 1) are there that do not contain a given substring?

I know my binary string is composed of exactly $n$ $1$s and $m$ $0$s. How many such strings are possible, if we add the constraint that they must not contain a specific given substring $S$ (whose ...
1
vote
2answers
193 views

Why are bitstrings without 00 of length n equals $Fib_{n+2}$?

EDIT: $B_{n}$ denotes the number of bitstrings of length n without 00. So I've been studying Discrete Math, and I came across the proof that $B_{n} = f_{n+2}$. What I do not understand about this is, ...