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)

Some new i found

Integers Set nth bit

x | (1<<n)

Unset nth bit

x & ~(1<<n)

Toggle nth bit

x ^ (1<<n)

Round up to the next power of two

unsigned int v; //only works if v is 32 bit v--; v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; v++;

Round down / floor a number

n >> 0

5.7812 >> 0 // 5

Get the maximum integer

int maxInt = ~(1 << 31); int maxInt = (1 << 31) - 1; int maxInt = (1 << -1) - 1; int maxInt = -1u >> 1;

Get the minimum integer

int minInt = 1 << 31; int minInt = 1 << -1;

Get the maximum long

long maxLong = ((long)1 << 127) - 1;

Multiply by 2

n << 1; // n*2

Divide by 2

n >> 1; // n/2

Multiply by the mth power of 2

n << m;

Divide by the mth power of 2

n >> m;

Check Equality

This is 35% faster in Javascript

(a^b) == 0; // a == b !(a^b) // use in an if

Check if a number is odd

(n & 1) == 1;

Exchange (swap) two values

//version 1 a ^= b; b ^= a; a ^= b;

//version 2 a = a ^ b ^ (b = a)

Get the absolute value

//version 1 x < 0 ? -x : x;

//version 2 (x ^ (x >> 31)) - (x >> 31);

Get the max of two values

b & ((a-b) >> 31) | a & (~(a-b) >> 31);

Get the min of two values

a & ((a-b) >> 31) | b & (~(a-b) >> 31);

Check whether both numbers have the same sign

(x ^ y) >= 0;

Flip the sign

i = ~i + 1; // or i = (i ^ -1) + 1; // i = -i

Calculate 2n

1 << n;

Whether a number is power of 2

n > 0 && (n & (n - 1)) == 0;

Modulo 2n against m

m & ((1 << n) - 1);

Get the average

(x + y) >> 1; ((x ^ y) >> 1) + (x & y);

Get the mth bit of n (from low to high)

(n >> (m-1)) & 1;

Set the mth bit of n to 0 (from low to high)

n & ~(1 << (m-1));

Check if nth bit is set

if (x & (1<<n)) { n-th bit is set } else { n-th bit is not set }

Isolate (extract) the right-most 1 bit

x & (-x)

Isolate (extract) the right-most 0 bit

~x & (x+1)

Set the right-most 0 bit to 1

x | (x+1)

Set the right-most 1 bit to 0

x & (x-1)

n + 1

-~n

n - 1

~-n

Get the negative value of a number

~n + 1; (n ^ -1) + 1; if (x == a) x = b; if (x == b) x = a;

x = a ^ b ^ x;

Swap Adjacent bits

((n & 10101010) >> 1) | ((n & 01010101) << 1)

Different rightmost bit of numbers m & n

(n^m)&-(n^m) // returns 2^x where x is the position of the different bit (0 based)

Common rightmost bit of numbers m & n

~(n^m)&(n^m)+1 // returns 2^x where x is the position of the common bit (0 based)

Floats

These are techniques inspired by the fast inverse square root method. Most of these are original.

Turn a float into a bit-array (unsigned uint32_t)

#include <stdint.h> typedef union {float flt; uint32_t bits} lens_t; uint32_t f2i(float x) { return ((lens_t) {.flt = x}).bits; } Caveat: Type pruning via unions is undefined in C++; use std::memcpy instead.

Turn a bit-array back into a float

float i2f(uint32_t x) { return ((lens_t) {.bits = x}).flt; }

Approximate the bit-array of a positive float using frexp

frexp gives the 2n decomposition of a number, so that man, exp = frexp(x) means that man * 2exp = x and 0.5 <= man < 1.

man, exp = frexp(x); return (uint32_t)((2 * man + exp + 125) * 0x800000);

Caveat: This will have at most 2-16 relative error, since man + 125 clobbers the last 8 bits, saving the first 16 bits of your mantissa.

Strings

Convert letter to lowercase:

OR by space => (x | ' ') Result is always lowercase even if letter is already lowercase eg. ('a' | ' ') => 'a' ; ('A' | ' ') => 'a'

Convert letter to uppercase:

AND by underline => (x & '') Result is always uppercase even if letter is already uppercase eg. ('a' & '') => 'A' ; ('A' & '_') => 'A'

Invert letter's case:

XOR by space => (x ^ ' ') eg. ('a' ^ ' ') => 'A' ; ('A' ^ ' ') => 'a'

Letter's position in alphabet:

AND by chr(31)/binary('11111')/(hex('1F') => (x & "\x1F") Result is in 1..26 range, letter case is not important eg. ('a' & "\x1F") => 1 ; ('B' & "\x1F") => 2

Get letter's position in alphabet (for Uppercase letters only):

AND by ? => (x & '?') or XOR by @ => (x ^ '@') eg. ('C' & '?') => 3 ; ('Z' ^ '@') => 26

Get letter's position in alphabet (for lowercase letters only):

XOR by backtick/chr(96)/binary('1100000')/hex('60') => (x ^ '') eg. ('d' ^ '') => 4 ; ('x' ^ '`') => 24

Miscellaneous

Fast color conversion from R5G5B5 to R8G8B8 pixel format using shifts

R8 = (R5 << 3) | (R5 >> 2) G8 = (R5 << 3) | (R5 >> 2) B8 = (R5 << 3) | (R5 >> 2) Note: using anything other than the English letters will produce garbage results