Questions tagged [bit-strings]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
21 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 ...
0
votes
0answers
43 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 ...
1
vote
0answers
29 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 '...
5
votes
3answers
124 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, ...
-2
votes
2answers
28 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 ...
1
vote
2answers
31 views

How to compute the $k$ least significant bits?

Suppose we have an integer $n$. How can I compute the $k$ least significant bits of $n$? For $k = 1$ we could just compute $n \bmod 2$, but I am not sure whether this is the best way to do this and it ...
-1
votes
3answers
177 views

Maximum number after AND operation

Help me to solve this You are given an array of $N$ numbers say $[A_1, A_2, \dots, A_n]$. Let us define a function $$F(x)=\sum_{i=1}^n (A_i \& x)$$ where & is bitwise AND operator. We needs to ...
1
vote
1answer
37 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 ...
0
votes
0answers
15 views

What would be the notation for this bit string with these characteristics look like?

Every block of 0s of length greater or equal to 3 cannot be followed by a block of 1s greater than or equal to three....As for blocks of 0s of length 2 or shorter, it must be followed by 1 mod 4 ...
1
vote
0answers
37 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, ...
0
votes
0answers
21 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), ...
0
votes
1answer
41 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 (...
0
votes
1answer
43 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 ...
0
votes
1answer
34 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 $...
0
votes
0answers
13 views

Field on 3 bit-string set with uniformly distributed mapping.

I'm wondering if it's possible to construct a set S consisting of three bit-strings and some uniform mapping F: S x S -> S (...
3
votes
2answers
36 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 ...
0
votes
0answers
27 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 ...
0
votes
0answers
10 views

Semi-metric on bit strings and degree of Cauchy-Schwarz inequality

Given elements $x,y \in GF(2^m) ,$ (e.g., bit strings of the form $x =011010, y= 110100$ for $m=6$), we define a semi-metric $d(x,y)$ by the largest distance between bits in $x,y$ that disagree. For ...
1
vote
0answers
62 views

How many bit strings of length 8 have at least twice as many 0’s as 1’s?

A problem on my discrete mathematics homework. My thought process is as follows: For there to be at least twice as many 0's as 1's, there can only be at most, 2 1's. Total possible strings: $2^8 = ...
0
votes
1answer
40 views

Recurrence Relations, understanding definition of formula

I have been trying to practice specific discrete math questions in my textbook and am having issues understanding how the terms are defined for a formula. Two examples that I do not understand. (1) ...
0
votes
1answer
56 views

Boolean function expression

I have an interesting problem. How do I express the following as a boolean function? HD ($2^4$, 1100) >=2 HD = Hamming distance $2^4$= {0000,0001,0010.....all 16 binary values} The answer ...
1
vote
4answers
418 views

How many bit strings of length 15 have:

If your are not sure what a bit string is here are some examples for this question: 000100000000000 111000000000000 011000000000000 101000000000000 001000000000000 110000000000000 ...
0
votes
2answers
130 views

Is there a combinatorially way to count the number of binary strings with consecutive $0$s?

How many strings are there that contain two consecutive $0$s? The typical way to approach this problem is using the Fibonacci sequence. But I'm wondering whether there's a way to do it purely ...
-1
votes
1answer
120 views

Parity function definition and intuition, characteristic function of a set.

I have a question of two (and a half) parts relating to parity functions. I) Pertaining to the definition of a parity function. II) Pertaining to the intuition behind checking some specific functions' ...
6
votes
1answer
79 views

What is the max length string that can be formed using k distinct characters so that all of its substrings are unique.

Given k distinct characters , what is the max length string that can be formed using these characters one or more time so that all the sub-string whose size is greater than one are unique. Eg - For k ...
0
votes
1answer
81 views

Recurrence relation of binary string with given condition

Get a recurrence relation for the number of binary string that do not contain exactly two 0s in a row. (As example, 010000 is acceptable, but 10011000 is not acceptable) My approach: I know that $2^...
2
votes
1answer
33 views

Is the prefix of power of three in binary representation contains all possible number combinations?

Let $S(x)$ be the string of positive integer $x$ in binary representation. Conjecture: For any positive integer $x$, there exists an integer $k$ such that string $S(x)$ is a prefix of string $S(3^k)$....
1
vote
2answers
301 views

How many bit strings contain exactly five $0$s and fourteen $1$s if every $0$ must be immediately followed by two $1$s?

How many bit strings contain exactly five $0$s and fourteen $1$s if every $0$ must be immediately followed by two $1$s? What I need help with: For this question, the answer is 126-bit strings. ...
2
votes
0answers
73 views

Thue-Morse Sequence riddle

The Thue-Morse sequence is constructed by replacing each instance of $0$ with the string $01$, and replacing $1$ with $10$. Equivalently, we can construct the sequence by successively appending the ...
1
vote
1answer
43 views

Entropy conservation of binary functions

In the merge function from https://github.com/ifdefelse/ProgPOW the authors talk about entropy maintaining functions that operate on bit-strings. Can someone explain what this is? I found literally ...
2
votes
1answer
52 views

How long can a string be before it must have considerable repeated substrings?

A considerable repeated substring $t \leqslant s \in \Sigma^*$ is a string of length $2$ that occurs at least 3 times disjointly within $s$ or a string of length $3$ or more that occurs at least $2$ ...
1
vote
1answer
37 views

radix number representation

I was reading an article where they have stated the following. Can someone explain how the L-notation is being calculated as 122. Thanks in advance.
3
votes
2answers
296 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'$...
3
votes
0answers
117 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
91 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
87 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
52 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 ...
0
votes
0answers
264 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
45 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
44 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 ...
1
vote
1answer
235 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
68 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 ...
0
votes
1answer
31 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
186 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
47 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$ ...
1
vote
4answers
1k 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
224 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
52 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
34 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 ...
1
vote
2answers
1k 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$?