Apr 03, 2017

Let's get down to the bit, boom boom pow. All about bit-wise operations. Want to codefight?

Kill K-th Bit (300/300)

You figured out that some numbers have a modified single digit in their binary representation. More specifically, in the given number n the kth bit from the right was initially set to 0, but its current value might be different. It's now up to you to write a function that will change the kth bit of n back to 0.

JavaScript

function killKthBit(n, k) {
  return ( (n >> k-1) & 1 ) == 0 ? n :
         n - Math.pow(2, k-1) ;
}

Array Packing (300/300)

You are given an array of up to four non-negative integers, each less than 256.

Your task is to pack these integers into one number M in the following way:

  • The first element of the array occupies the first 8 bits of M;
  • The second element occupies next 8 bits, and so on.

JavaScript

function arrayPacking(a) {
    var packedNum = '';
    for(var i=a.length-1; i >= 0; --i)
        packedNum += toByte(a[i]);
    return parseInt(packedNum,2);
}

function toByte(num){
    return ("00000000" + num.toString(2)).substr(-8);    
}

Range Bit Count (300/300)

You are given two numbers a and b where 0 ≤ a ≤ b. Imagine you construct an array of all the integers from a to b inclusive. You need to count the number of 1s in the binary representations of all the numbers in the array.

JavaScript

function rangeBitCount(a, b) {
    var ones = 0;
    for(var i=a; i<=b; ++i){ 
        // Using Hamming Weight algorithm
        // found at http://stackoverflow.com/questions/15233121/calculating-hamming-weight-in-o1
        var num_byte = i - ((i>>1) & 0x55555555);
        num_byte = (num_byte & 0x33333333) + ((num_byte>>2) & 0x33333333);
        ones += ((num_byte + (num_byte>>4) & 0xF0F0F0F) * 0x1010101) >> 24;
    }
    return ones;
}

Mirror Bits (300/300)

Reverse the order of the bits in a given integer.

JavaScript

function mirrorBits(a) {
    // Turn a to string, string to array, reverse, then join
    return parseInt( Array.from(a.toString(2)).reverse().join(""), 2);
}

Second-Rightmost Zero Bit (300/300)

Presented with the integer n, find the 0-based position of the second rightmost zero bit in its binary representation (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2^position_of_the_found_bit.

JavaScript

function secondRightmostZeroBit(n) {
  return (n | (n+1)) ^ ( (n | (n+1)) | ( (n | (n+1)) + 1) );
}

Swap Adjacent Bits (300/300)

You're given an arbitrary 32-bit integer n. Swap each pair of adjacent bits in its binary representation and return the result as a decimal number.

JavaScript

function swapAdjacentBits(n) {
  return ((n << 1) & 0xAAAAAAAA) | ((n >> 1) & 0x55555555) ;
}

Different Rightmost Bit (300/300)

You're given two integers, and m. Find position of the rightmost bit in which they differ in their binary representations (it is guaranteed that such a bit exists), counting from right to left.

Return the value of 2^position_of_the_found_bit (0-based).

JavaScript

function differentRightmostBit(n, m) {
  return (n^m) ^ ( (n^m) & ((n^m)-1) );
}

Equal Par of Bits (300/300)

You're given two integers, n and m. Find position of the rightmost pair of equal bits in their binary representations (it is guaranteed that such a pair exists), counting from right to left.

Return the value of 2^position_of_the_found_pair (0-based).

JavaScript

function equalPairOfBits(n, m) {
  return ~(n^m) & ((n^m)+1);
}