Questions tagged [bit-strings]
Use this tag for questions related to array data structures that compactly store bits.
124
questions
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$ ...
asked Aug 3 '19 at 2:08
CommutativeAlgebraStudent
17.3k5 gold badges30 silver badges72 bronze badges
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$?
