# Questions tagged [bit-strings]

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

92 questions
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 ...
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, ...
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 ...
40 views

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 ...
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 ...
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$ ...
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 ...
140 views

Actually i have no idea about this question.i know the definition of equivalence relations 1-) reflective 2-) symmetric 3-) transitive but not more :(
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 ...
132 views

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 ...
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 ...
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 ...
119 views

### Multiplying strings as polynomials

Interdisciplinary Question: How to approach the question and arrive at the solution?
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. ...
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?
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 ...
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 ...
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 ...
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 ...
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!
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} ...
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 ...
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, ...