Questions tagged [bit-manipulation]

The tag has no usage guidance.

13 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
38 views

Is this algorithm faster than any prior solution to “Generate All Balanced Parentheses”?

It's an old question: "Generate All Balanced Parentheses." The problem statement in short: given n pairs of parentheses, generate all combinations of well-formed parentheses strings of length 2n. A ...
2
votes
0answers
80 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
27 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
2answers
73 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 ...
1
vote
0answers
53 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
46 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

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
10 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
0answers
25 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
51 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
162 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
49 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 ...