Questions tagged [bit-manipulation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
40 views

Efficient way to implement a bit-wise counter that becomes 1 every (k*n)+i times

My question is about LeetCode "137.Single Number II": 137.Single Number II Given an integer array nums where every element appears three times except for one, which appears exactly once. ...
R. Javid's user avatar
  • 131
0 votes
3 answers
56 views

Is there an algorithm to implement N-input-gates using smaller gates?

To borrow part of a description from a similar but distinct question: there exist 2^(2^N) different functions which accept N binary inputs and return a 1 bit output. For the purposes of my question I ...
HappMacDonald's user avatar
1 vote
1 answer
48 views

Splitting a Larger Unsigned Integer into Summable Parts

I have a very strange (arbitrary) problem that I have been trying to wrap my head around, but have been struggling to figure out how to accomplish this. I'll use Rust but in a pseudo-code fashion, ...
Naftuli Kay's user avatar
0 votes
2 answers
116 views

Why is 2's complement used for representing negative numbers?

So I was reading the use complement operation in the digital logic and found, it is used to give additive inverse of the number and subtracting a number (like we do) is difficult for computer. So it ...
tbhaxor's user avatar
  • 142
0 votes
0 answers
36 views

Exact Definition of simple bit pattern?

I didn't find an exact description for this, but I know that any integer type is a simple bit pattern, it seems to me that the simple bit pattern should have a more exact description as I understand ...
Gor Madatyan's user avatar
1 vote
1 answer
71 views

Faster finding of a subset of bits with all combinations in the bitstrings

Assume that I have a bunch of bitsets (strings on $\{0,1\}$) of the same length, e.g.: 101110001 001001101 010101010 101001001 101010101 I want to find the largest ...
Dmitry's user avatar
  • 345
-2 votes
1 answer
107 views

Find Number of subsequences such that bitwise OR is same as sum

Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
abcd's user avatar
  • 1
4 votes
3 answers
4k views

Calculating XOR of all numbers from 1 to n: Why does this method work?

Given a number n, the task is to find the XOR of every number from 1 to n. Why does the following algorithm work? Find the remainder of n by moduling it with 4. If rem = 0, then XOR will be same as n....
MonkaS's user avatar
  • 89
0 votes
1 answer
128 views

Is "Bitwise Complement Operator" (~ tilde) distributive?

To be more precise, Is ~(a+b) = ~a + ~b? Here, "~" bitwise NOT operator. I ran into this question while thinking about ...
siv2r's user avatar
  • 1
0 votes
1 answer
70 views

Number of bit string interpretations correct?

Suppose you are given a bit string $B[1 ... n]$. Now, suppose that some bits are just padding bits conveying no information, the rest of the bits may be permuted and some meaningful (that is, non-...
coderodde's user avatar
-3 votes
1 answer
154 views

Identify the missing number in a set given its superset

Given a set B and B’s superset A, if B is missing 1 number (let’s y) but don’t know which number it is, how to find that number? That is, B’ = B \ {y}, for some unknown element y B = A \ {x}, for ...
Paul Yu's user avatar
0 votes
1 answer
52 views

Why is the file size smaller than what I calculated?

The question is the conversion from an animation to a video file with the following attributes: Frame rate:24 fps Resolution:320*240 pixels Color depth:24 bits Length of video: 60s Bit rate: 500kbps I ...
user1039203's user avatar
0 votes
1 answer
112 views

What property of XOR makes this algorithm work?

I'm having trouble figuring out why using XOR for this problem works; I've done it a couple of times by-hand, and can't really seem to understand it. I know that XOR is commutative and associative, ...
discreteboy's user avatar
1 vote
3 answers
424 views

How bits translated into text on the screen?

recently i started studying computer science and computer graphics, and one question really haunts me. Mby someone can explain this. How bit patterns become translated into (for example ) text. I know ...
Artyom Vorontsov's user avatar
1 vote
0 answers
46 views

Efficient bit-level implementation of Boolean polynomials with few variables

A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form $$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$...
BubbleZ's user avatar
  • 11
0 votes
1 answer
451 views

Number of subsequence's with same values of bitwise and, or and xor

GeeksForGeeks We are given an array arr of $n$ element. We need to count number of non-empty subsequences such that these individual subsequences have same values of bitwise AND, OR and XOR. For ...
Devesh jha's user avatar
-2 votes
1 answer
139 views

What is the reason for this contradiction about the size of the char type?

the size of one char in C is 4 bytes, however to define an 'A' character we use the sum of two values like this expression here: or in other way i want to say that the char is 4 bytes size, but in ...
meddhiaka's user avatar
1 vote
2 answers
73 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 ...
Henry Zhu's user avatar
  • 125
0 votes
2 answers
1k 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, ...
anonuser01's user avatar
1 vote
1 answer
36 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 ...
rbtrht's user avatar
  • 275
0 votes
1 answer
95 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 ...
ultimate cause's user avatar
2 votes
1 answer
56 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 ...
Kolya Ivanov's user avatar
3 votes
4 answers
5k 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 ...
Paul Razvan Berg's user avatar
0 votes
1 answer
949 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 ...
x89's user avatar
  • 167
0 votes
0 answers
33 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 ...
Andrew's user avatar
  • 1
2 votes
1 answer
238 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...
Reggie Simmons's user avatar
0 votes
2 answers
176 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$...
helluvaq's user avatar
1 vote
1 answer
779 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)...
Semo's user avatar
  • 25
1 vote
1 answer
119 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 ...
Niels's user avatar
  • 13
1 vote
1 answer
93 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 ...
user3563894's user avatar
2 votes
1 answer
107 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)....
Christopher Miller's user avatar
1 vote
1 answer
114 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 ...
TheEnvironmentalist's user avatar
0 votes
1 answer
165 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 ...
desmond.belphegor's user avatar
2 votes
2 answers
146 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. ...
nat nav's user avatar
  • 33
1 vote
1 answer
54 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: ...
macros's user avatar
  • 45
0 votes
0 answers
66 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 ...
iago-lito's user avatar
  • 195
2 votes
1 answer
216 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 ...
Niraj Raut's user avatar
1 vote
2 answers
94 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? ...
casper's user avatar
  • 11
-1 votes
3 answers
724 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: ...
DeadManProp's user avatar
2 votes
3 answers
88 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. ...
xyf's user avatar
  • 127
1 vote
1 answer
59 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: ...
joe's user avatar
  • 113
1 vote
2 answers
51 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 ...
Lance's user avatar
  • 2,193
0 votes
2 answers
2k 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 ...
Umer Farooq's user avatar
0 votes
0 answers
30 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 ...
Naghi's user avatar
  • 101
2 votes
1 answer
45 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 ...
Albert Hendriks's user avatar
0 votes
1 answer
156 views

Maximum value of $\{ i \land n \mid a \leq i \leq b \}$

I was doing problems in "Leetcode" and found a problem that I could not solve. Given a non-negative number $n$ and two non-negative numbers $a$ and $b$, consider every number $i$ such that $a \leq i \...
Sandeep's user avatar
  • 47
0 votes
3 answers
184 views

Minimum number of ways to write a string

Consider the following question There are K magical pens (numbered 1 through K). You are given strings P1,P2,…,PK (each of which consists of characters from 'a', 'b', …, 't') ; for each valid i, the ...
nope's user avatar
  • 9
1 vote
1 answer
4k views

ip/tcp packet decoding without wireshark

How can we manually read and interpret packets properly without using wireshark? Now from the Ethernet header I know that the Destination MAC Address should be at the 5th byte (after converting bits/...
x89's user avatar
  • 167
2 votes
2 answers
36 views

Data structure for or-lookups over bit-field associations maps

For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality. Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{...
fakedrake's user avatar
  • 131
2 votes
1 answer
532 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/...
ChocolateOverflow's user avatar