rishabhk965's blog

By rishabhk965, history, 4 years ago, In English

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.

  • Vote: I like it
  • +24
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

that's so nice !