Bit Manipulation TRICKS

Revision en1, by rishabhk965, 2020-03-29 17:08:32

Bit manipulation is generally faster because CPU directly supports these operations. Some of the very common use case bit hacks:

1) Swapping two numbers:

x = x ^ y
y = x ^ y
x = x ^ y

How does it work?

Because of XOR property y^(x^y) = x. and x^(x^y) = y. (be aware that it is not actually faster than the general extra variable swap, as it can’t achieve instruction parallelism.)

2) Find min(max) of two numbers(very efficient method):

min = y ^ ((x^y) & -(x < y))

How it works? (lets assume x = 3 and y = 4, min should be x)

First the last part: -(x < y), if x < y it becomes -(1). 2’s complement if of -1 is 1111(how? 1’s complement+1). If x > y it becomes -(0) => 0000.

Second part: ((x^y) & 1111) anding any number with all one return the same number, so (x^y) & 1111 => (x^y).

Third and final part, y ^ (x^y) by xor property it should be equal to x.

3) Mod of sum of two numbers:(normal method for mod of n is (x+y) % n).

z = x + y
m = z - (n & -(z >= n))

How it works?

Is simple terms, z — (n) iff z >= n, else z.

Tell us more in the comments.

Tags #bitmask, tips-and-tricks

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rishabhk965 2020-03-29 17:08:32 1163 Initial revision (published)