Equal Pair of Bits

Description:

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 2position_of_the_found_pair (0-based).

Example

For n = 10 and m = 11, the output should be
equalPairOfBits(n, m) = 2.

1010 = 10102, 1110 = 10112, the position of the rightmost pair of equal bits is the bit at position 1 (0-based) from the right in the binary representations.
So the answer is 21 = 2.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer n

    Constraints:
    0 ≤ n ≤ 230.

  • [input] integer m

    Constraints:
    0 ≤ m ≤ 230.

  • [output] integer

Tests:
Solution:

int equalPairOfBits(int n, int m) {
    return n + m + 1 & ~m - n ;
}

Different Rightmost Bit

Description:

You’re given two integers, n 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 2position_of_the_found_bit (0-based).

Example

For n = 11 and m = 13, the output should be
differentRightmostBit(n, m) = 2.

1110 = 10112, 1310 = 11012, the rightmost bit in which they differ is the bit at position 1 (0-based) from the right in the binary representations.
So the answer is 21 = 2.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer n

    Constraints:
    0 ≤ n ≤ 230.

  • [input] integer m

    Constraints:
    0 ≤ m ≤ 230,
    n ≠ m.

  • [output] integer

Tests:
Solution:

int differentRightmostBit(int n, int m){
    return -~((~(n^m))^((~(n^m))+1))/2 ;
}

Swap Adjacent Bits

Description:

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.

Example

  • For n = 13, the output should be
    swapAdjacentBits(n) = 14.

    1310 = 11012 ~> 11102 = 1410.

  • For n = 74, the output should be
    swapAdjacentBits(n) = 133.

    7410 = 010010102 ~> 100001012 = 13310.
    Note the preceding zero written in front of the initial number: since both numbers are 32-bit integers, they have 32 bits in their binary representation. The preceding zeros in other cases don’t matter, so they are omitted. Here, however, it does make a difference.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer n

    Constraints:
    0 ≤ n < 230.

  • [output] integer

Tests:
Solution:

int swapAdjacentBits(int n) {
    return (((n & 0x2AAAAAAA) >> 1) | ((n & 0x15555555) << 1)) ;
}

Second-Rightmost Zero Bit

Description:

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 2position_of_the_found_bit.

Example

For n = 37, the output should be
secondRightmostZeroBit(n) = 8.

3710 = 1001012. The second rightmost zero bit is at position 3 (0-based) from the right in the binary representation of n.
Thus, the answer is 23 = 8.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer n

    Constraints:
    4 ≤ n ≤ 230.

  • [output] integer

Tests:
Solution:

int secondRightmostZeroBit(int n) {
    return -~((n-~(n^(n+1))/2)^(n-~(n^(n+1))/2+1))/2 ;
}

Mirror Bits

Description:

Reverse the order of the bits in a given integer.

Example

  • For a = 97, the output should be
    mirrorBits(a) = 67.

    97 equals to 1100001 in binary, which is 1000011 after mirroring, and that is 67 in base 10.

  • For a = 8, the output should be
    mirrorBits(a) = 1.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer a

    Constraints:
    5 ≤ a ≤ 105.

  • [output] integer

Tests:
Solution:

int mirrorBits(int a) {
    int b = 0;
    while (a > 0) {
        b <<= 1;
        b |= a & 1;
        a >>= 1;
    }

    return b;
}

Range Bit Count

Description:

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.

Example

For a = 2 and b = 7, the output should be
rangeBitCount(a, b) = 11.

Given a = 2 and b = 7 the array is: [2, 3, 4, 5, 6, 7]. Converting the numbers to binary, we get [10, 11, 100, 101, 110, 111], which contains 1 + 2 + 1 + 2 + 2 + 3 = 11 1s.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer a

    Constraints:
    0 ≤ a ≤ b.

  • [input] integer b

    Constraints:
    a ≤ b ≤ 10.

  • [output] integer

Tests:
Solution:

int rangeBitCount(int a, int b) {
    if(0<=a && a<=b) {
        int total = 0;
        for (int i = a; i <= b; i++) {
            int t = i;
            while (t != 0) {
                if((t&1)==1)
                total++;
                t >>= 1;
            }
        }

        return total;
    }
    else
    {
        throw new ArgumentOutOfRangeException();
    }
}

Array Packing

Description:

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.

Return the obtained integer M.

Note: the phrase “first bits of M refers to the least significant bits of M – the right-most bits of an integer. For further clarification see the following example.

Example

For a = [24, 85, 0], the output should be
arrayPacking(a) = 21784.

An array [24, 85, 0] looks like [00011000, 01010101, 00000000] in binary.
After packing these into one number we get 00000000 01010101 00011000(spaces are placed for convenience), which equals to 21784.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.integer a

    Constraints:
    1 ≤ a.length ≤ 4,
    0 ≤ a[i] < 256.

  • [output] integer

Tests:
Solution:

int arrayPacking(int[] a) {
    if(1 <= a.Length && a.Length <= 4) {
        int result = 0;
        for(int index=0;index<a.Length;index++) {
            if(a[index]>256 || a[index]<0) {
                throw new ArgumentOutOfRangeException();
            }
            else {
                result += a[index] << 8 * index;
            }
        }
        return result;
    }
    else {
        throw new ArgumentOutOfRangeException();
    }
}