Difference between revisions of "Interview Preparation Bit Fiddling"

/* Find the highest bit that has been set in a uint32 variable */
uint32_t find_highest_bit_num(uint32_t num)
{
    for(int i = 31; i >= 0; i--) {
        if (num & (1 << i)) {
            return i;
        }
    }
    return 0;
}

/* Well, that is too slow, so find the highest bit faster */
int find_highest_bit_num(uint32_t num)
{
    uint16_t high = (num >> 16);
    uint16_t low  = (num >> 0 );
    if (high) {
        return find_highest_bit_num_16(high);
    } else {
        return find_highest_bit_num_16(low);
    }
}
/* Same idea, except this function finds highest in 16-bit number */
int find_highest_bit_num_16(uint16_t num)
{
    uint8_t high = (num >> 8);
    uint8_t low  = (num >> 0);
    if (high) {
        return find_highest_bit_num_8(high);
    } else {
        return find_highest_bit_num_8(low);
    }
}
/* This is the final step, which ends up in a lookup table.
 * Your interviewer will be looking for "lookup table" answer.
 */
int find_highest_bit_num_8(uint8_t num)
{
    /* Create a lookup table of a number and its highest bit set */
    const int8_t table[256] = { -1, /* No bit set */
                                 0, /* 1 */
                                 1, /* 2 */
                                 1, /* 3 */
                                 2  /* 4 */
                               }
    return table[num];
}

/* Invert a number's bit at a particular bit position */
uint32_t invert_bit(uint32_t num, uint32_t bit_pos)
{
    return num xor (1 << bit_pos); // xor is a valid operator
    return (num ^ (1 << bit_pos)); // Same result, ^ is same as XOR
}

uint8_t swap_nibble(uint8_t num)
{
    uint8_t high_nibble = (num >> 4);
    uint8_t low_nibble  = (num & 0x0F);
    return (low_nibble << 4) | (high_nibble);
}

unsigned int Bits_swap(unsigned int z)
{
    // Get all even bits of z.
    // The number 0xAAAAAAAA is a 32 bit number with all even bits set as 1 and all odd bits as 0.
    unsigned int even_bits = z & 0xAAAAAAAA;

    // Get all odd bits of z
    // The number 0x55555555 is a 32 bit number with all odd bits set as 1 and all even bits as 0.
    unsigned int odd_bits  = z & 0x55555555;

    even_bits >>= 1;  // Right shift even bits
    odd_bits <<= 1;   // Left shift odd bits

    return (even_bits | odd_bits); // Combine even and odd bits
}

// Driver program to test above function
int main()
{
    unsigned int x = 56; // 00111000

    // Output is 52 (00110100)
    printf("%u ", Bits_swap(x));

    return 0;
}

int bitSwapConversion (int x, int y)
{
	int count = 0;
	for(int z = x^y; z != 0; z = z >> 1)
	{
		count += z & 1;
	}
	return count;
}

int bitSwapConversion(int x, int y)
{
	int count = 0;
	for (int z = x^y; z != 0; z = z & (z-1))
	{
		count++;
	}
	return count;
}

int bitsInsert(int x, int y, int a, int b)
{
	/* Create a mask value to clear bit a through b in x.
	 * Example: a = 0, b = 4. Result should be 11100000.
	 * For simplicity, I use just 8 bits for example.
	 */
	int allOnes = ~0;

	//Insert 1s before position b, then all 0s.
	int left = allOnes << (b+1); // left = 11100000

	// Insert 1s after bit position a.
	int right = ((1 << a) - 1); // right =  00000000

	int mask_num = left | right; // mask = 11100000

	int clear_X = x & mask_num; // clear bits a through b
	int shift_Y = y << a; // Move Y into correct position

	return clear_X | shift_Y;
}

int nextGreater(int x)
{
	// Compute c0 and c1
	int c = x;
	int c0 = 0;
	int c1 = 0;
	
	while (((c & 1) == 0) && (c != 0))
	{
		c0++;
		c >>= 1;
	}
	
	while (((c  & 1) == 1))
	{
		c1++;
		c >>= 1;
	}
	
	//Error if x = 11..1100...00, because there is no bigger number with 
	//same number of 1s.
	if (c0 + c1 == 31 || c0 + c1 == 0)
	{
		return -1;
	}
	
	int p = c0 + c1; // Rightmost non trailing 0.

	x |= (1 << p); // Flip rightmost non trailing 0.
	x &= ~((1 << p) - 1); // Clear all bits to the right of p
	x |= (1 << (c1 - 1)) -1; // Insert c1-1 ones on the right and we are done
	return x;
}