Bit manipulation

• char :

  • 1 bytes, 8 bits

  • ASCII: 0< char <127

• int:

  • 4bytes, 32bits

• double, float:

  • 8bytes, 32bits

1.Flip operation

char x = 'A' // 01000001
char y = ~x; // 10111110

2.And operation

char x = 'A';  // 01000001
char y = 'L';  // 01001100
char z = x & y;// 01000000

3.Or operation

char x = 'A';  // 01000001
char y = 'L';  // 01001100
char z = x | y;// 01001101

4.XOR operation

• 兩個同時等於0, 兩個不同時等於1

• b ^ 11111111 = ~b

• b ^ b = 0

char x = 'A';  // 01000001
char y = 'L';  // 01001100
char z = x ^ y;// 00001101

5.Shift operation

char x = 'A';  // 01000001
char z = x >> 3;// 00001000 shift each bit 3 places to the right
char y = x << 3;// 00001000 shift each bit 3 places to the left

6.Get the Nth bit

• 用Nth為1的check bit做and運算, 再shift left

(b & 00010000) << 4

int get_nth_bit(int num, int n)
{
    int check_bit = 1 << n;
    int and_bit = num & check_bit;
    return and_bit == check_bit;
}

7.Set the Nth bit to 1

int set_nth_bit_to_1(int num, int n)
{
    int set_bit = 1 << n;
    return num | set_bit;
}

8.Print bits an integer

• Shift it left sizeof(int)*8 - 1 times

void print_bits(int num)
{
    unsigned int check_bit = 1 << (sizeof(int) * 8 - 1);
    while(check_bit != 0)
    {
        int result = num & check_bit;
        if (result == check_bit)
        {
            printf("%d\n", 1);
        }
        else
        {
            printf("%d\n", 0);
        }
        check_bit = check_bit >> 1; 
    }
    printf("\n");
}

9.Count the number of 1 bits

• The simple way is very similar to the print bits example: O(N)

• binary subtraction: n & (n - 1): O(1)

int count_ls_optimized(int num)
{
    int count = 0;
    while(num != 0)
    {
        num = num & (num - 1);
        count++;
    }
    return count++;
}

10.Reverse the bits in an integer

int reverse_bits(int num)
{
    int reverse_num = 0;
    unsigned int count = sizeof(int)*8 -1;
    while(num != 0)
    {
        int last_bit = num & 1;
        reverse_num = reverse_num | last_bit;
        reverse_num = reverse_num << 1;
        num = num >> 1;
        count--;
    }
    
    reverse_num = reverse_num << count;
    return reverse_num;
}