Questions tagged [bit-manipulation]

The tag has no usage guidance.

18 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...