UInIQ
1/9/2017 - 9:16 PM
js-bitwise-hacks.md
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).
Table of Contents
- Toggle switch
- Variable swap
- Math.pow
- Determine if an integer is a power of 2
- Round up to the next highest power of 2
- Determine if two integers have opposite signs
- Check if the integer is even or odd
- Integer division and multiplication
- Modulus division without a division operator
- Math.floor
- Math.max
- Check if value cannot be parsed to a number
- Convert colors from RGB to Hex format
- Get the difference between two hex values
- Create array of bits of a number
- Counting bits in a 32-bit integer
- Merge bits from two values according to a mask
- Test if the n-th bit is set
- Set the n-th bit
- Unset the n-th bit
- Toggle the n-th bit
- Turn off the rightmost 1-bit
- Isolate the rightmost 1-bit
- Right propagate the rightmost 1-bit
- Isolate the rightmost 0-bit
- Turn on the rightmost 0-bit
- Checking that all bits are the same
- Identify trailing zeroes
- Identify rightmost set and trailing unset
Toggle switch
var v = 1;
v ^= 1; // => 0
v ^= 1; // => 1
v ^= 1; // => 0
v ^= 1; // => 1
Variable swap
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
Check if the integer is odd or even
if (v & 1) {
// v is odd
}
else {
// v is even
}
Why? The righmost or zeroth bit of odd number is always set. Back to top
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.floor
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);
// => '#bada55'
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 mask = 128;
var bits = [];
while (mask > 0) {
mask >>= 1;
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
}
Set the n-th bit
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.
Toggle the n-th bit
v ^ (1 << n);
Right propagate the rightmost 1-bit:
v | (v - 1);
Isolate the rightmost 0-bit:
~v & (v + 1);
Turn on the rightmost 0-bit
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
Turn off the rightmost 1-bit
v & (v - 1);
Why? The rightmost bit of odd number is always set. Back to top
Isolate the rightmost 1-bit
v & (-v);
Identify rightmost set and trailing unset
!!(v ^ (v - 0x01));