Home › Algorithms

Bit Fiddling

Swapping variables without additional space

Wed, 07/19/2006 - 23:06 — tekpool

Swapping variables is a very common operation used it tons of algorithms like sorting etc. The most common and obvious technique is using of a temporary variable to swap values between two variables

void swap(int &i, int &j)
{
   int temp = i;
   i = j;
   j = temp;
}

Instead of writing a separate function for each data type, you could write a MACRO or templatize the function.

Swapping without using a temporary variable is an age old trick and there are a few ways to do this. You could use of the basic arithmetic operations like +,-,/,*

Bit Count: Parallel Counting - MIT HAKMEM

Wed, 09/28/2005 - 07:22 — tekpool

Q: Find the number of set bits in a given integer

Sol: Parallel Counting: MIT HAKMEM Count

HAKMEM (Hacks Memo) is a legendary collection of neat mathematical and programming hacks contributed mostly by people at MIT and some elsewhere. This source is from the MIT AI LABS and this brilliant piece of code orginally in assembly was probably conceived in the late 70's.

 int BitCount(unsigned int u)
 {
         unsigned int uCount;

         uCount = u
                  - ((u >> 1) & 033333333333)
                  - ((u >> 2) & 011111111111);
         return

Bit Count: Unset Bit Iterator

Wed, 09/28/2005 - 07:17 — tekpool

Q: Find the number of set bits in a given integer

Sol: Unset Bit (0's) Iterator

This is similar to the Set Bit Iterator method, expect that all bits are toggled before iteration, and uCount is decremented whenever a set bit (originally unset) is encountered.

int BitCount (unsigned int u)
{
        //number of bits in unsigned int
        unsigned int uCount= 8 * sizeof(unsigned int);

        // Toggle bits
        u ~= (unsigned int) -1 ;
        for(; u; u&=(u-1))
            uCount--;

        return uCount ;
}

Bit Count: Set Bit Iterator

Wed, 09/28/2005 - 07:14 — tekpool

Q: Find the number of set bits in a given integer

Sol: Set Bit (1's) Iterator

Here, the line u &= u-1 flips the highest set bit in each iteration, until there are no more set bits.

int BitCount (unsigned int u)
{
         unsigned int uCount=0 ;

         for(; u; u&=(u-1))
            uCount++;

         return uCount ;
}

Running time is proportional to the number set bits, Useful when there are less number of set bits in the number

Bit Count: Looping through the Bits

Wed, 09/28/2005 - 07:05 — tekpool

Q: Find the number of set bits in a given integer

Sol: Looping through all the bits

In this approach, the number is looped through all its bits one by one using a right shift, and checking if the low bit is set, in every iteration by AND’ing with 0x1u

int BitCount(unsigned int u)
{
           unsigned int uCount = 0;

           for(; u; u>>=1)
                uCount += u & 0x1u;

           return uCount;
}

Bit Count: Pre-Computing Bits

Tue, 09/27/2005 - 04:46 — tekpool

Q: Find the number of set bits in a given integer?

Sol: Pre-Computing Bits

static unsigned int NumBits8Bit[256] ;

//Precompute this array of size 256, each element in the array denoting the number of bits in a char (0x00 to 0xff). Then separate divide the number of interest into 4 blocks of 8 bits each by masking the last 8 bits (ANDing it with 0xffU) and right shifting by 8 bits each time. Sum up the count and return


int BitCount (unsigned int u)
{

return NumBits8Bit [u & 0xffU]

Syndicate content