Questions tagged [bit-manipulation]
The bit-manipulation tag has no usage guidance.
48
questions
2
votes
1answer
42 views
Prime checking and factorization with just bit cheking
I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/...
1
vote
2answers
42 views
If XOR of n distinct numbers is ANDed over one of the number, the result would be zero
Say we Have n distinct numbers
x1,x2,....xn
And we xor the result
xoredResult = x1^x2...^xn
And if we AND(&) with one ...
3
votes
1answer
93 views
Minimum XOR for queries
I was asked the following question in an interview.
Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \...
3
votes
1answer
47 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}...
0
votes
2answers
33 views
Fundamental motivation behind the use of bits and binary representation
This is a naive question, but what makes binary representation special from a theoretical standpoint and from the standpoint of information theory?
If for technical reasons building ternary computers ...
1
vote
1answer
22 views
Names of power-of-two bit operations on bitsets that would not assume any number interpretation
Three commonly used functions when it comes to bit manipulation are :
is_pow2: Checking that an integer is a power-of-two (only one bit is set): $00010000 \...
1
vote
2answers
51 views
Dividing 2 integers with some constraints
This a problem i came across while practicing binary search. Here is the problem:
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
...
0
votes
0answers
19 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 ...
1
vote
1answer
30 views
How to solve Assigment problem on SPOJ? [closed]
Problem Link - Assign .This problem is known as assignment problem.
I read few solutions Here is one and they are trying to solve it using Bit-masking and DP .I tried and thought hard to ...
0
votes
0answers
36 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 ...
2
votes
1answer
66 views
find maximum sum of xors
we are given an Array
Array size <= 10^4 .
0 <= A[i] <= 15
We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum ...
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?
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 ...
0
votes
0answers
11 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
16 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 ...
3
votes
1answer
101 views
Is is possible to determine if a given number is xor combination of some numbers?
I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$...
2
votes
1answer
165 views
Can I simplify successive XOR operations?
I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions).
We have a rectangle of known ...
4
votes
2answers
345 views
Converting a number from N to 0 in binary
Trying to solve this problem since 2 days. Still unable to figure out even a basic approach.
Given a number $N$ in binary ($1$ to $10^5$), we need to convert it to $0$ using only 2 operations. ...
1
vote
2answers
231 views
Find the bitwise AND of a subarray closest to given number
It was a question I was asked in an online assessment for a company.
Please help me in this question-
Given an array, $A$ of size $N$ and an integer $P$ , find the subarray $B = A[i \dots j]$ such ...
1
vote
2answers
112 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 ...
2
votes
0answers
88 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
84 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)
...
0
votes
2answers
54 views
How “add” could be implemented in only bitshift operations
Typically, add/subtract/multiply/divide are primitive operations in an Instruction Set Architecture (ISA). I am interested to know if they can instead be implemented efficiently using only bitshift ...
1
vote
1answer
32 views
What are 'Butterfly Combinations' and why are they called this way?
In some scientific work describing Discrete Fourier Transform-algorithms, such as the well-known Cooley-Tukey algorithm, I came across the term 'Butterfly operations' and 'Butterfly combinations', ...
1
vote
2answers
59 views
What kind of operations can we do with bits?
I wonder if there are more things we can do with bits aside from NOT, AND, OR, XOR operations? I got this question from my teacher and I'm not really sure. How about bit shifting ">>"? Could we count ...
1
vote
2answers
43 views
Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X
The beauty of a number is defined as follows :-
...
1
vote
1answer
87 views
Given a bitstring generate all bitstring with n flipped bits
For an algorithm I need to be able to iterate over all bit strings where $k$ bits are flipped given a bit string with length $n$ and $n \geq k$. For instance let's say I have the bit string $1001$ and ...
0
votes
0answers
34 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} (...
1
vote
0answers
18 views
Find $b$-th bit of a number $n$, with sign [closed]
Let $n\in\mathbb{Z}$ and $0\leq b\leq63$, $b\in\mathbb{N}$. Find the $b$-th bit for the number n on it's $64$ bit representation with sign.
and $T$ be the number of test cases.
This is my attempt:
<...
3
votes
1answer
35 views
How are the prime numbers encoded in Knuth's example of fitting primes into memory cache?
Could somebody please help me understand what is going on here (in plain English)? I think that $(k \mathbin{\&} 63)$ has the effect of modular division. Is that right? How are the primes encoded /...
3
votes
1answer
67 views
How to distinguish between bits?
I read a post about differences between synchronous and asynchronous transmission modes.
That post has a picture about how bits flows from terminal to computer in async mode.
But how computer can ...
0
votes
1answer
339 views
Bytes from integer using bitwise operators
So I am extremely confused with using bitwise shifts used to extract the bytes from an integer. I find that if I do something like this...
...
0
votes
2answers
54 views
Easiest way to find y in $x \text{ xor } y = z$ with given $x \text{ and } z$
Let's say we have given two numbers $x, z$, and we need to find another number $y$ such that $x \text{ xor } y = z$. The xor ( exclusive or ) is bitwise operation: xor table
.
I know that this can be ...
0
votes
1answer
134 views
How to count number of 1s of the first k positions in a bitset (bitmap)?
Input: Given a bitset $b$, which is is an array of 0s and 1s, of length $L$, and a positive integer $k$.
Output: the total number of 1s in the first $k$ position of $b$.
Obviously it can be done in $...
0
votes
0answers
62 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
1answer
56 views
Test a bit substring function
How do we test the following function?
bits(bitstring, i, j)
which returns a copy of the substring from i to ...
1
vote
0answers
57 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
35 views
Convert (x + y = z) to propositional logic formula for 8-bit numbers
(Note: this was asked in the cstheory stackexchange, but I was told this is a more appropriate place for it.)
I have three 8-bit 2's-complement numbers (X, Y, and Z). I want to find a propositional ...
0
votes
2answers
285 views
Fast searching through bitarray?
I've been thinking for some time but can't figure a way out.
I have big bitarray i.e. 1000+ items of 10_000 bits strings, I'm searching them now linearly. (currently it is stored in one chunk of ...
0
votes
0answers
172 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 ...
2
votes
1answer
36 views
Difference between CNOT and 2nd bit bitflip
I understand how the outcome of each is supposed to be different, but in matrix form are these gates not the same? The CNOT matrix negates the second bit regardless of the input of the first.
0
votes
2answers
118 views
UInt128 - Compute the product of two UInt128's that are each represented by two UInt64's?
I have a struct like this:
struct UInt128 {
UInt64 s1;
UInt64 s2;
}
In this struct, s1 represents the highest 64-bits ...
1
vote
1answer
844 views
Hamming distance and parity
For an Hamming code of $n$ bit there are $k$ bit reserved for the data and $p$ bit for the parity where $p$ is the minimum integer for which the following inequation is satisfied: $$2^p \geqslant p + ...
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 ...
0
votes
0answers
50 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 ...
1
vote
1answer
75 views
How to retrieve reset bit in constant time in a bit array
In a game application there is a session id assigned to each player every time they start a new session.
Session id's are always unique and there can be billion users of this game. Whenever a user ...
2
votes
1answer
186 views
For given set of integers, find and count the pairs with maximum value of bitwise or
Let's say we have given set of integers $A = \{x_1, x_2, x_3, x_4, \dots, x_n\}$, consisting of exactly $n$ values, all of them positive integers. Now the problem is to find the maximum value of ...
1
vote
1answer
40 views
How to access the bit at a particular index? [closed]
How do I access the bit at a particular index in a number using shift operator.
Say the number is $n$.
Let the index be $i (i: 0 \le i < n).$
Rightmost bit is $0$.
The only thing I can ...
