Questions tagged [bit-strings]
Use this tag for questions related to array data structures that compactly store bits.
211 questions
8
votes
2
answers
384
views
How do I cook my food efficiently
What is the optimal strategy for flipping N pork tenderloins?
The Setup
Today, I decided to pan-sear some pork tenderloin. I sliced the piece into $N=15$ roughly identical cylinders and arranged them ...
- 252
0
votes
0
answers
56
views
Find probability a bit is 0 after k inserts
I am reading about an analysis of a construct called Bloom filter that has a capacity/buffer of $$m$$ bits and uses k hashes per element inserted to find the position in that m bit buffer.
When trying ...
- 1,737
2
votes
0
answers
44
views
Efficient cover of $\mathbb{Z}_N$ with bit shift operation
I have a simple electronics device that has no processor in the usual sense, but it has a finite memory, call it $N$ bits, with a bit-shifting operation. We got onto the question of whether we could ...
- 1,474
0
votes
1
answer
67
views
Defining bitwise and in terms of bitwise masking
I need help completing a proof that defines bitwise-and in terms of arithmetic and bitwise-masking.
Let $\&$ denote the bitwise-and operation on natural numbers and $\preceq$ denote the bit-...
- 3,582
1
vote
0
answers
63
views
Formula for an alternating sum over weight $ w $ bit strings [duplicate]
Let $ b_0 $ be a length $ n $ bit string of Hamming weight $ w_0 $. The sum
$$
\sum_{wt(b)=w} (-1)^{b ~\cdot~ b_0}
$$
over all length $ n $ bit strings $ b $ of some fixed Hamming weight $ w $ has $ \...
- 10.3k
0
votes
2
answers
127
views
Independence of XORed random variables
Let $s_1 , \cdots , s_l \sim U\{0, 1\}^n$ - independent random variables uniformly distributed over $\{0, 1\}^n, J_1 \subset \{1 , \cdots , l\}, J_2 \subset \{1 , \cdots , l\}$.
Define $r_{J_1} = \...
user824478
1
vote
0
answers
79
views
Arbitrary bitstrings
I was going to approach this question using the pigeonhole method and need to confirm if it's correct.
Given a bitstring B = b1, …, b1200 of length 1200, we need to prove that B contains at least two ...
- 11
3
votes
0
answers
94
views
How many bits are needed to distinguish functions over bit vectors given a maximum number of twos-complement addition operations?
Say we have two distinct functions $f(x_1, ..., x_n)$ and $g(x_1, ..., x_n)$, where each $x_i$ is a bit vector of length $B$. Each function consists of an arbitrary number of bitwise operations like ...
3
votes
1
answer
92
views
Suppose $A$ is an infinitely long binary string. Does $A$ contain a square, $XX,$ where $\vert X\vert =k,$ for infinitely many $k?$
Suppose $A$ is an infinitely long binary string. Does $A$ contain a
square, $XX,$ where $\vert X\vert =k,$ for infinitely many $k?$
Proof by contradiction or finding a counter-example is probably the ...
- 25.2k
1
vote
4
answers
235
views
Determine the number of binary strings of length $n$ that do not contain two consecutives $1$s and contain at least three consecutives $0$s
Given binary strings of length $n$ that do not contain two consecutives $1$s, I want to determine by a formula the number of strings that contain at least three consecutives $0$s. How can I do this?
I ...
3
votes
1
answer
70
views
Finding permutation of given set of decimal digits with largest number of trailing zero bits in representation
I'm trying to find a way of determining a way to represent a longish (26 character) string of digits in such a way that it contains the greatest number of consecutive trailing zero bits. The order of ...
- 131
0
votes
0
answers
79
views
Looking for a bijection between the integers and finite binary strings
Let $A$ be the set of all finite binary strings. Example elements are "", "0", "1", "00", "01", ...
I'm looking for a bijection between the integers ...
- 259
0
votes
0
answers
71
views
Revision on solutions regarding combinations of bit strings
How many bit strings of length 65 are there such that the bit string contains exactly twenty-five 0s, additionally, the bit string corresponding to the first eight positions must have exactly two 1s ...
- 217
3
votes
2
answers
194
views
Steps on solving part b of the bit-string exercise?
This is the exercise:
How many bit strings of length $77$ are there such that
a.) the bit
string has at least forty-six $0$s and at least twenty-nine $1$s, and also
the bit string corresponding to ...
- 217
-2
votes
1
answer
82
views
Generate set of numbers containing 3 consecutive 1, but without the elements of the previous set [closed]
So I have this specific problem that I couldn't figure out. I want to create a set $F_n$ containing all bitstrings that has 3 consecutive 1s, but not those that are already contained in all the ...
- 723