Questions tagged [bit-manipulation]
The bit-manipulation tag has no usage guidance.
16
questions with no upvoted or accepted answers
3
votes
1answer
62 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
0answers
210 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
51 views
Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?
I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational ...
1
vote
0answers
33 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
146 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
73 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
44 views
Efficient triangular decomposition of an integer
Euclidean division is an iterative process
that has been made super-efficient at the CPU level, right?
Its specification is that if I do (q, r) = f(n, d), I get ...
0
votes
2answers
66 views
How are bitwise operators used in normalisation of floating-point numbers?
After having spent a significant amount of time googling this topic, I am still struggling to confidently answer the following question:
...
0
votes
0answers
29 views
How computer understand to either represent the original bits or two's complement as value?
Important note
I know that this question may seem too simple for you scientists; however, here is the best place that I know to post it.
Question
Suppose we have an ...
0
votes
0answers
13 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
2answers
172 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
74 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
112 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
196 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
52 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 ...
