Bitwise tricks

bitwise-operators.md

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)

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

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

Thanks