bit function

Let f(k) = y where k is the y-th number in the increasing sequence of non-negative integers with the same number of ones in its binary representation as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6) = 3 and so on. Given k >= 0, compute f(k).

Analysis:

Ex:
// series with 2 bits
00000011 1
00000101 2
00000110 3
00001001 4
00001010 5
00001100 6
00010001 7

// series with 3 bits
00000111 1
00001011 2
00001101 3
00001110 4
00010011 5

//------------- PROBABLY NOT SO OPTIMAL ---------------
#include "stdio.h"
#include "stdlib.h"

/**
 * O(n) algorithm, where n is the number of bits set
 * This algorithm works on the fact that when 1 is subtracted,
 * there exists a bit k, below which all the bit places get changed
 * so, num & num-1 will clear all the bits below the bit k.
 * ( to see this enable PrintBinary() function below )
 * */
size_t CountBits(size_t num)
{
    size_t count = 0;
    while (num)
    {
        //PrintBinary(num);
        num &= num-1;
        ++count;
    }
    return count;
}
/**
 * This is O(1) algorithm, but uses a lookup table.
 * Initially fill the lookup table with the bit count
 * then look into it :)
 * we can bring down the memory even further by using a lookup
 * table of size 16 (4 bits instead of 8 )
 * */
size_t lookup[256] = {};
void InitLookup()
{
    for( int i = 0; i <= 0xFF; ++i)
        lookup[i] = CountBits(i);
}

size_t CountBits_O1(size_t num)
{
    size_t count = lookup[num&0xFF] +
        lookup[ (num >> 8) & 0xFF ] +
        lookup[ (num >> 16) & 0xFF ] +
        lookup[ (num >> 24) & 0xFF ];

    return count;
}

void FindInSeries(size_t k)
{
    const size_t bit_count = CountBits_O1(k);
    size_t seq_pos = 0;
    // This is the start of the series
    size_t start = ( 1 << bit_count ) - 1;

    printf(" start %d, bit_count %d \n", start, bit_count );

    for ( size_t i=start; i != k; ++i)
    {
        if ( CountBits_O1(i) == bit_count )
        {
            ++seq_pos;
            printf("%d ", i);
        }
    }

    ++seq_pos;

    printf("\n f(%d) = %d \n", k, seq_pos);
}

int main (int argc, char* argv[])
{
    size_t num = atoi( argv[1] );
    InitLookup();
    FindInSeries(num);
    return 0;
}

Add numbers in base n

Give an approach/code to add numbers in base n.

Answer:

After adding each digit, the sum%n will appear in the sum, and sum/n will be carried forward.  

Palindrome Bit Representation

Check if binary representation of an int is a palindrome or not.
Answer:

Approach I:
Reverse the first word of the number and compare with the second word.

Apporach II:
Use a lookup table which contains the reverse of numbers from [0,0xFF]
#define IS_PALINDROME(num) ( (num & 0xFF) == lookup[num>>24] ) && (num>>8 & 0xFF) == lookup[num>>16] )

Mulitply by 7

Give a fast way to multiply a number by 7.

Answer:

#define MULTIPLY_BY_7(num) (num << 3) - num

Bit changes required to convert one int to another

Given two integers A & B. Determine how many bits required to convert A to B.

Answer:

 CountBits(A^B); 

bit pattern check

I want to see if all the ones in a number appear on the right side of the number and all zeros appear on the left, how can I do this most efficiently? (i.e. 00000111 is true but 100010 is false)

Answer: Check if num+1 is a power of 2

Power of 2

Give a one-line C expression to test whether a number is a power of 2.

Anwer:

#define IS_POW_OF_2(n) !(n & (num-1))

Reverse the bits of an unsigned integer.

Reverse the bits of an unsigned integer.

Anwer:

Solution 1: The normal loop technique.
Solution 2: Use the lookup table, as used in counting the bits of a unsigned integer.¹

Bits set in a number

Write Program to count the number of bits set in a number.

Answer:

/**
 * Program to count the number of bits in a program
 * */

#include "stdio.h"
#include "stdlib.h"

void PrintBinary(size_t num)
{
    for( int i = 31; i >=0; --i )
        if ( num & ( 1 << i) )
            printf("1");
        else
            printf("0");
    printf("\n");
}

/**
 * O(n) algorithm, where n is the number of bits set
 * This algorithm works on the fact that when 1 is subtracted,
 * there exists a bit k, below which all the bit places get changed
 * so, num & num-1 will clear all the bits below the bit k.
 * ( to see this enable PrintBinary() function below )
 * */
size_t CountBits(size_t num)
{
    size_t count = 0;
    while (num)
    {
        //PrintBinary(num);
        num &= num-1;
        ++count;
    }
    return count;
}

/**
 * This is O(1) algorithm, but uses a lookup table.
 * Initially fill the lookup table with the bit count
 * then look into it :)
 * we can bring down the memory even further by using a lookup
 * table of size 16 (4 bits instead of 8 )
 * */
size_t lookup[256] = {};
void InitLookup()
{
    for( int i = 0; i <= 0xFF; ++i)
        lookup[i] = CountBits(i);
}

size_t CountBits_O1(size_t num)
{
    size_t count = lookup[num&0xFF] +
        lookup[ (num >> 8) & 0xFF ] +
        lookup[ (num >> 16) & 0xFF ] +
        lookup[ (num >> 24) & 0xFF ];

    return count;
}

int main (int argc, char* argv[])
{
    size_t num = atoi( argv[1] );
    printf("Bit count O(n) %d \n", CountBits(num) );
    InitLookup();
    printf("Bit count O(1) %d \n", CountBits_O1(num) );
    return 0;
}

Divisible by 3?

Give a method if a number is divisible by 3 without using the modulo operator.

Answer:

Sum the digits recursively until we are left with 3 or 6 or 9

bool IsDivisible(int num)
{
    int sum_of_digits = 0;
    if ( num < 10 )
    {
        if ( num == 3 || num == 6 || num == 9 )
            return true;
        else
            return false;
    }
    while(num)
    {
        sum_of_digits += num % 10;
        num = num / 10;
    }
    return IsDivisible(sum_of_digits);
}

Exchange the bits at even and odd positions

Write code to exchange the bits at even and odd positions in a number.

Answer:

/**
 * Program to exchange the bits at even and odd positions
 * */
#include "stdio.h"
#include "stdlib.h"

void PrintBinary(size_t num)
{
    for( int i = 31; i >=0; --i )
        if ( num & ( 1 << i) )
            printf("1");
        else
            printf("0");
    printf("\n");
}

size_t SwapBits(size_t num)
{
    /* Program to reverse the bits of a number */

    return ( (num << 1) & 0xAAAAAAAA ) |
        ( (num >> 1 & 0x55555555) );
}

int main(int argc, char* argv[])
{
    for ( int i = 1; i <= argc-1; ++i )
    {
        size_t num = atoi(argv[i]);
        PrintBinary(num);
        PrintBinary(SwapBits(num));
    }
    return 0;

}