Questions tagged [bit-manipulation]
The bit-manipulation tag has no usage guidance.
18
questions with no upvoted or accepted answers
3
votes
1answer
51 views
Evaluating predicate on binary strings
Consider two unknown binary strings $$X = x_{1} x_{2} \dots x_{n^{2}}, \quad Y = y_{1} y_{2} \dots y_{n^{2}}, \quad x_{i}, y_{i} \in \{0, 1\} .$$ We may request a string $Z = z_{1} z_{2} \dots z_{n^{2}...
3
votes
0answers
37 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 ...
2
votes
1answer
23 views
Data structure for or-lookups over bit-field associations maps
For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality.
Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{...
2
votes
0answers
155 views
Count number of pairs of elements in an array whose bitwise OR is equal to a given integer
Given an integer array and an integer $k$, we have to count the number of pairs of elements from the array whose bitwise OR is $k$ in $O(n)$ time complexity. How could this be done?
1
vote
0answers
32 views
Least computationally expensive bitwise addition
I am familiar with the oft-cited method of bitwise addition using XOR and left shift for the carry, applied recursively. I was wondering if this is the least computationally expensive way to achieve ...
1
vote
0answers
115 views
If only using bit-shifts can produce a Turing-machine, or if you need more bitwise operations
So you can have One Instruction Set Computers. But typically these instructions have rather complicated underlying implementations.
addition (addleq, add and branch if less than or equal to zero)
...
1
vote
0answers
62 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
9 views
L-System coordinate conversion (as opposed to drawing): Extending the Hilbert Space Filling Curve
I have been reading for some time about L-Systems, and specifically the Hilbert Space filling curve. I am interested in writing a function to convert upper-triangular matrix coordinates into an 1-...
0
votes
0answers
22 views
Quantization in deep neural networks
I am following this tutorial about quantization in tensorflow.
tutorial 1
tutorial 2
Tutorial 1, describes the quantization formula as:
My question is, if you have 3 floating point values ...
0
votes
0answers
58 views
How to create a register from DFF bit components?
I am a new student at computer architectures and my current task is to create a register of 4 bits.
We were a working DFF and my bit component seems to work.
My DFF:
My bit:
I tried to create the ...
0
votes
0answers
44 views
Slice one bit from a number, and move it to the beginning of the number
In a number, select a bit at a position k, remove it ("slice it"), and move it to the leftmost bit of the number.
Number: 1001001
k: 4
result: 1100001
How would a computer best do that?
0
votes
0answers
12 views
Number of bits for scalar product signal
let's consider two vectors $v_1[i]$, $v_2[i]$, for $i = 0, 1, ... , N$.
Suppose you want to calculate the scalar product between them: it is simply the sum of all $v_1[i] * v_2[i]$ terms $(i=0,...,N)$...
0
votes
0answers
18 views
How to optimally select free-list in a custom allocator?
I have a program where I cannot afford to use standard memory allocators because they use MAP_PRIVATE and not MAP_SHARED for the ...
0
votes
2answers
149 views
Given matrix, count paths visiting each number exactly once
We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in ...
0
votes
0answers
71 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} (...
0
votes
0answers
88 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
0answers
188 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 ...
0
votes
0answers
51 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 ...
