# Questions tagged [bit-manipulation]

The tag has no usage guidance.

75 questions
Filter by
Sorted by
Tagged with
45 views

### Why is the time complexity of the Bit Manipulation solution to Binary Addition O(M + N)?

I am trying to understand why the time complexity of the Bit Manipulation solution (https://leetcode.com/problems/add-binary/solution/) to the Binary Addition problem is O(M + N), where M and N are ...
30 views

### Complexity of n & (n - 1) should be O(1) or O(log n)?

I'm looking at the methods posted in https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ for checking whether n is a power of 2. Method 5, ...
34 views

### A small question about generating random variable with geometric distribution

I was reading Professor Knuth's Volume 2 (page 136) about generating a geometrically distributed random variable $N$ (with $p$ as the probability of success). Basically, the idea is to generate a ...
65 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 ...
51 views

### Maximize AND on a sequence of XORs

Problem We are given 2 arrays a and b both of length n. We build a third array ...
2k views

### How to find the largest power of two divisor of a given integer?

Given an integer $x$, I need to find the largest power of two $p = 2^n$ that divides $x$ such that the remainder is zero. When $x$ is zero, the algorithm should return zero. For odd numbers, it should ...
33 views

### while loop for bitwise conversion program

int counter(char c){ int count = 0; while (c!=0){ if((c & 1) !=0) count++; c = c >> 1; } } I am trying to understand a ...
21 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 ...
41 views

### Compressing a bit string when I know how many 1s and 0s there are

Say I have a 256 bit bit-string, and I know that there are 16 ones and 240 zeros. I know that this bit string can be compressed, because there are only 256 choose 16...
74 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$...
131 views

### Must a Turing machine tape be binary?

I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7)...
31 views

### Book CS:APP, using bit set and bit clear

Okay so I'm going through a book CS:APP. I'm in chapter 2. And problem 2.13 talks about how the Digital Equipment VAX computer used bis (bit set) and bic (bit clear) instead of Boolean operations AND ...
57 views

### How can I prove or disprove that the following function is bijection?

For a research project, I tried to prove or disprove that a function called xxhash128_low is a bijection from 64 bit unsigned integer to 64 bit unsigned integer. I have shown that it is sufficient to ...
55 views

### Is the following Greedy algorithm to generate Gray Codes always correct?

I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites)....
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 ...
84 views

### How to prove that n&(n-1) and n&(-n) respectively returns and removes the least significant bit?

In a code, I saw someone use: n&(n-1) to get the least significant bit of n ⇒ 101000 will return 1000 ...
86 views

### Right most set bit O(log N)

I tried to do the problem Find first set bit in Geeks for Geeks, and this is the code I used. ...
28 views

### XOR operation to swap to value without additional variable

I'm breaking my mind to find a good explanation to split two variables with the XOR operation. The operation is the following: ...
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 ...
74 views

### If the integer representation used is “0 through 4,294,967,295 (2^32 − 1)”, so does this mean the register cannot handle negative numbers?

From Wikipedia: A 32-bit register can store 2^32 different values. The range of integer values that can be stored in 32 bits depends on the integer representation used. With the two most common ...
44 views

### Simple question about signed integer multiplication

If you have a signed integer int x = any And then state that x < 0 Is the following statement true or false? ...
113 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: ...
61 views

### Determining the number of iterations needed to find the number of bits in an integer

I'm trying to understand the complexity/number of iterations needed to determine the number of bits in an integer. ...
58 views

### Is there a name for X when X bitwise OR Y is Y?

I'm wondering if there is a mathematical or computer science term for a number X such that Y | X = Y? For example: ...
35 views

### Is there a way to store an arbitrarily big BigInt in a bit sequence, only later to convert it into a standard BigInt structure?

I am trying to imagine a way of encoding a BigInt into a bit stream, so that it is literally just a sequence of bits. Then upon decoding this bit stream, you would generate the standard BigInt sort of ...
457 views

### Intelligent use of XOR operator to find missing number

I've come across the following problem on leetcode & tried to solve it with the following code however there seems to be an even better solution that takes advantage of XOR. Leetcode has a ...
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 ...
24 views

### Uniquely identifying bits

Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them? Is this problem NP-Hard? For example, given the $4$ unique ...
155 views

68 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/...
55 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 ...
935 views

45 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 ...
26 views

426 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 ...
1k 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. ...
491 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 ...
189 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 ...
216 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?