People who code: we want your input. Take the Survey

Questions tagged [bit-manipulation]

The tag has no usage guidance.

18 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
1answer
65 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
39 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
213 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
1answer
73 views

Create binary numbers with a described pattern

I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$...
1
vote
0answers
52 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
35 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
173 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
79 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
1answer
60 views

Shuffling Bits For Uniform Distribution

I am writing a hashing algorithm to be used in the key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to ...
0
votes
0answers
20 views

What is the order of magnitude of bitwise operations involved in a SHA-256 hash?

Specifically, how many bitwise operations (approximately, could be just order of magnitude) occur each time a Bitcoin ASIC miner performs a SHA-256 hash in typical mining computation, i.e. as it ...
0
votes
0answers
52 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
98 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
2answers
185 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
116 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
200 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 ...