Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Bitwise tricks

Inspired by this article. Neat tricks for speeding up integer computations.

Note: cin.sync_with_stdio(false); disables synchronous IO and gives you a performance boost. If used, you should only use cin for reading input (don't use both cin and scanf when sync is disabled, for example) or you will get unexpected results.

Multiply by a power of 2
x = x << 1; // x = x * 2
x = x << 6; // x = x * 64
Divide by a power of 2
x = x >> 1; // x = x / 2
x = x >> 3; // x = x / 8
Swap integers without a temporary variable
a ^= b; // int temp = b
b ^= a; // b = a
a ^= b; // a = temp
Increment / Decrement (slower but good for obfuscating)
i = -~i; // i++
i = ~-i; // i--
Sign flipping
i = ~i + 1; // or
i = (i ^ -1) + 1; // i = -i
Modulo operation if divisor is power of 2
x = 131 & (4 - 1); // x = 131 % 4
Check if an integer is even or odd
(i & 1) == 0; // (i % 2) == 0
Equality check
(a^b) == 0; // a == b
Absolute value
x < 0 ? -x : x; // abs(x)
(x ^ (x >> 31)) - (x >> 31) // abs(x)
Equal sign check (both ints are pos or neg)
a ^ b >= 0; // a * b > 0
Rounding, ceiling, flooring
(x + 0.5) >> 0; // round(x)
(x + 1) >> 0; // ceil(x)
x >> 0; // floor(x)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment