Skip to content

Instantly share code, notes, and snippets.

@dideler
Created April 12, 2012 08:25
Show Gist options
  • Save dideler/2365607 to your computer and use it in GitHub Desktop.
Save dideler/2365607 to your computer and use it in GitHub Desktop.
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)
@ClydeFrog04
Copy link

ClydeFrog04 commented Jan 28, 2021

This is a great reference, but unless I'm missing something, the ceiling function does not work if the input x is 1. Expected value is 1, but the output is 2

@akinkajuoyo
Copy link

what of | bitwise operator and how it is used in python?

@maruf-sarker
Copy link

Thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment