UInIQ
1/9/2017 - 9:16 PM

## JavaScript Bitwise Hacks

It assumes the highest positive signed 32-bit float value for numbers. In other words, 2147483647 (or 0x7FFFFFFF or 2^31-1).

var v = 1;

v ^= 1; // => 0
v ^= 1; // => 1
v ^= 1; // => 0
v ^= 1; // => 1

var x = 1;
var y = -2;

x ^= y;
y ^= x;
x ^= y;

x; // => -2
y; // => 1

### Math.pow

Bitwise left shift operator can be a replacement for Math.pow() when dealing with bases of 2:

Math.pow(2, 12) === 1 << 12
// => true

### Determining if an integer is a power of 2

v && !(v & (v - 1));

### Round up to the next highest power of 2

var v = 5; // unsigned integer;

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
++v;

// => 8

### Determine if two integers have opposite signs

NOTE: fails for 0 and -0

var x = 1;
var y = 1;

(x ^ y) < 0;
// => false

if (v & 1) {
// v is odd
}
else {
// v is even
}

### Integer multiplication and division

20.5 << 1; // <~> 20 * 2
// => 40

20.5 >> 1; // <~> 20 / 2
// => 10

### Modulus division without a division operator

#### Modulus division by 1 << s

var n = 20;          // unsigned integer; numerator
var s = 3;           // unsigned integer; power of 2
var d = 1 << s;      // unsigned integer; d will be one of: 1, 2, 4, 8, 16, 32, ...
var m = n & (d - 1); // unsigned integer; m will be n % d

m === 20 % 8;
// => true

#### Modulus division by (1 << s) - 1

var n = 20;           // unsigned integer; numerator
var s = 3;            // unsigned integer > 0; power of 2
var d = (1 << s) - 1; // unsigned integer; so d is either 1, 3, 7, 15, 31, ...).
var m;                // unsigned integer; n % d goes here.

for (m = n; n > d; n = m) {
for (m = 0; n; n >>= s) {
m += n & d;
};
};

// Now m is a value from 0 to d,
// but since with modulus division we want m to be 0 when it is d.
m = (m == d) ? 0 : m;

m === 20 % 7;
// => true

### Math.max

var x = 2410;
var y = 19;

Math.max(x, y) === (x ^ ((x ^ y) & -(x < y)));
// => true

Math.min(x, y) === (y ^ ((x ^ y) & -(x < y)));
// => true

### Check if value cannot be parsed to a number

NOTE: the result will always be zero

~~NaN
// => 0

~~'hello'
// => 0

~~{}
// => 0

~~[]
// => 0

~~function doSmth(){}
// => 0

~~false
// => 0

~~true
// => 1

NaN >>> 0
// => 0

'hello' >>> 0
// => 0

({} >>> 0)
// => 0

[] >>> 0
// => 0

(function doSmth(){}) >>> 0
// => 0

false >>> 0
// => 0

true >>> 0
// => 1

### Convert colors from RGB to Hex format

var color = { r: 186, g: 218, b: 85 };

var rgb2hex = function(r, g, b) {
return '#' + ((1 << 24) + (r << 16) + (g << 8) + b).toString(16).slice(1);
}

rgb2hex(color.r, color.g, color.b);

### Get the difference between two hex values

var a = 0xF0; // 240
var b = 0xFF; // 255

~a & b;
// => 15

### Create array of bits of a number

var num = 5;
var index = 0;

var bits = [];
index++;
bits.push((mask & num ? 1 : 0));
};

bits;
// => [0, 0, 0, 0, 0, 1, 0, 1]

parseInt(bits.join(''), 2);
// => 5

### Counting bits in a 32-bit integer

#### The naive way

var v = 5;
var count; // accumulates the total bits set in v

for (count = 0; v; v >>= 1) {
count += v & 1;
};

// The naive approach requires one iteration per bit, until no more bits are set.
// So on a 32-bit word with only the high set, it will go through 32 iterations.

#### Brian Kernighan's way

var v = 5;
var count;

for (count = 0; v; count++) {
v &= v - 1; // clear the least significant bit set
};

// Brian Kernighan's method goes through as many iterations as there are set bits.
// So if we have a 32-bit word with only the high bit set, then it will only go once through the loop.

#### The best approach

var v = 5;
var count;

v = v - ((v >> 1) & 0x55555555);                        // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);         // temp
count = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

### Merge bits from two values according to a mask

var x;    // unsigned integer to merge in non-masked bits
var y;    // unsigned integer to merge in masked bits
var mask; // unsigned integer; 1 where bits from y should be selected; 0 where from x.
var r;    // unsigned integer; result of (x & ~mask) | (y & mask) goes here

r = x ^ ((x ^ y) & mask);

// This shaves one operation from the obvious way of combining two sets of bits according to a bit mask.

### Test if the n-th bit is set

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

v | (1 << n);

### Unset the n-th bit

v & ~(1 << n);

// b = a | ~(1 << n);
// Shift 1 n times left, complement it or it with a and then put it into a new variable b.

v ^ (1 << n);

v | (v - 1);

~v & (v + 1);

v | (v + 1);

### Checking that all bits are the same

(v & (v + 0x01)) == 0x00;

//////////////////////////

(1 & (1 + 0x01)) == 0x00;
// => true

(0 & (0 + 0x01)) == 0x00;
// => true

(2 & (2 + 0x01)) == 0x00;
// => false

(15 & (15 + 0x01)) == 0x00;
// => true

### Identify trailing zeroes

!!(~v & (v - 0x01));

//////////////////////////

!!(~15 & (15 - 0x01));
// => false

!!(~13 & (13 - 0x01));
// => false

!!(~0 & (0 - 0x01));
// => true

!!(~1 & (1 - 0x01));
// => false

!!(~2 & (2 - 0x01));
// => true

v & (v - 1);