Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [bit-strings]

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

1
vote
2answers
191 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, ...
0
votes
2answers
236 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
1answer
50 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 ...
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
1answer
138 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 :(
0
votes
1answer
21 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
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
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
0answers
99 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 ...
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 ...
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$)...
2
votes
0answers
117 views

Multiplying strings as polynomials

Interdisciplinary Question: How to approach the question and arrive at the solution?
1
vote
0answers
69 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 ...
1
vote
0answers
49 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 ...
1
vote
0answers
62 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$...
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 ...
1
vote
0answers
46 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
0answers
45 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
105 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 ...
0
votes
0answers
16 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
0answers
59 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 ...
0
votes
0answers
25 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 ...
0
votes
0answers
320 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 ...
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 ...
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 $...
0
votes
0answers
41 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 ...
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 ...