Questions tagged [bit-manipulation]
The bit-manipulation tag has no usage guidance.
0
votes
0answers
18 views
Find xor sum of all pairs raised to power of 3
We are given array $A$ of $N$ integers each in the range $1 \leq A_i \leq 2^{30}$, that is we can write each integer with at most 30 bits. The target is to compute $\sum_{1\leq i \leq N,1\leq j<i} (...
1
vote
0answers
14 views
Find $b$-th bit of a number $n$, with sign [closed]
Let $n\in\mathbb{Z}$ and $0\leq b\leq63$, $b\in\mathbb{N}$. Find the $b$-th bit for the number n on it's $64$ bit representation with sign.
and $T$ be the number of test cases.
This is my attempt:
<...
3
votes
1answer
32 views
How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?
Could somebody please help me understand what is going on here (in plain English)? I think that $(k \mathbin{\&} 63)$ has the effect of modular division. Is that right? How are the primes encoded /...
0
votes
0answers
28 views
Comparison Algorithm on Numbers of Arbitrary Base
Given two numbers of base $B$, $x = (abc...)_{B}$ and $y = (pqr...)_{B}$ where $0 \leq a,b,c,\ldots,p,q,r,\ldots < B$ are the digits of the numbers, is there an algorithm to compute $(a \geq p) \&...
3
votes
1answer
53 views
How to distinguish between bits?
I read a post about differences between synchronous and asynchronous transmission modes.
That post has a picture about how bits flows from terminal to computer in async mode.
But how computer can ...
0
votes
1answer
50 views
Bytes from integer using bitwise operators
So I am extremely confused with using bitwise shifts used to extract the bytes from an integer. I find that if I do something like this...
...
0
votes
2answers
48 views
Easiest way to find y in $x \text{ xor } y = z$ with given $x \text{ and } z$
Let's say we have given two numbers $x, z$, and we need to find another number $y$ such that $x \text{ xor } y = z$. The xor ( exclusive or ) is bitwise operation: xor table
.
I know that this can be ...
0
votes
1answer
45 views
How to count number of 1s of the first k positions in a bitset (bitmap)?
Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$.
Output: the total number of 1s in the first $k$ position of $b$.
Obviously it can be done in $...
0
votes
0answers
38 views
Variable bytes (bit arrays) and flipping single bits?
My interest is strictly theoretical at this point, but ultimately applied.
Is there any problem, theoretically, with defining a byte with m bits, and flipping single bits to connote T/F for a given ...
0
votes
1answer
27 views
Test a bit substring function
How do we test the following function?
bits(bitstring, i, j)
which returns a copy of the substring from i to ...
1
vote
0answers
38 views
Difference in bit vectors
I have to write an algorithm for a following problem. I have a function that has 2 parameters: an array of 32 bit unsigned whole numbers - bit vectors [ARR] and distance[dist]. We need to find how ...
0
votes
0answers
10 views
Compressed bitvector with fast append and iterate through ones
Is there a compressed bit vector structure that has iteration through indexes of ones and efficient (comparable performance to uncompressed bitvector w/ length) append of small numbers of bits?
0
votes
0answers
138 views
Design an expanding opcode to allow all the following to be encoded in a 32-bit instruction
We are given: 80 instructions with no addresses or registers and should design an expanding opcode in a 32-bit instruction.
I was thinking about having only zeros of 4 bits in a 32-bit instruction.
...
0
votes
1answer
22 views
Convert (x + y = z) to propositional logic formula for 8-bit numbers
(Note: this was asked in the cstheory stackexchange, but I was told this is a more appropriate place for it.)
I have three 8-bit 2's-complement numbers (X, Y, and Z). I want to find a propositional ...
0
votes
2answers
121 views
Fast searching through bitarray?
I've been thinking for some time but can't figure a way out.
I have big bitarray i.e. 1000+ items of 10_000 bits strings, I'm searching them now linearly. (currently it is stored in one chunk of ...
0
votes
0answers
129 views
algorithm - maximum pair-wise xor
Given two integers m and n where m < n find the maximum pair-wise xor sum.
The question is how to choose m distinct integers from 1 to n such that using those m numbers yields the maximum pair-wise ...
2
votes
1answer
29 views
Difference between CNOT and 2nd bit bitflip
I understand how the outcome of each is supposed to be different, but in matrix form are these gates not the same? The CNOT matrix negates the second bit regardless of the input of the first.
0
votes
2answers
53 views
UInt128 - Compute the product of two UInt128's that are each represented by two UInt64's?
I have a struct like this:
struct UInt128 {
UInt64 s1;
UInt64 s2;
}
In this struct, s1 represents the highest 64-bits ...
1
vote
1answer
369 views
Hamming distance and parity
For an Hamming code of $n$ bit there are $k$ bit reserved for the data and $p$ bit for the parity where $p$ is the minimum integer for which the following inequation is satisfied: $$2^p \geqslant p + ...
4
votes
0answers
36 views
Bridging inductive natural number and bits?
Most popular representation for the natural numbers in type systems is:
Inductive nat : Set :=
| 0 : nat
| S : nat -> nat.
However, digital computers ...
0
votes
0answers
44 views
Avoiding overflow when comparing between 16-bit numbers
Let's say I have a 16-bit number system. and let $a, b$ a 16-bit numbers in this system.
I know that the numbers I can represent in this system are between $−32,768$ and $32,767$.
Let's say I want ...
1
vote
1answer
55 views
How to retrieve reset bit in constant time in a bit array
In a game application there is a session id assigned to each player every time they start a new session.
Session id's are always unique and there can be billion users of this game. Whenever a user ...
2
votes
1answer
70 views
For given set of integers, find and count the pairs with maximum value of bitwise or
Let's say we have given set of integers $A = \{x_1, x_2, x_3, x_4, \dots, x_n\}$, consisting of exactly $n$ values, all of them positive integers. Now the problem is to find the maximum value of ...
1
vote
1answer
39 views
How to access the bit at a particular index? [closed]
How do I access the bit at a particular index in a number using shift operator.
Say the number is $n$.
Let the index be $i (i: 0 \le i < n).$
Rightmost bit is $0$.
The only thing I can ...
