Tuesday, March 22, 2011

Convert integer to binary or bit string

Question: write a function to convert an integer into a bit string. For example, if input is 2, the output is "00000000000000000000000000000010" if the system is 32-bit, "0000000000000010" if the system is 16-bit and so on.

Solution: the strategy here is to use bitwise manipulation and convert one bit at a time to character. We look at the right most bit and if it is a 0 bit, we add '0' character into our bit string. Otherwise, we add '1' character into our bit string. Here is the code in C++:

char* int2bin(int num)
{
  const int BITS_PER_BYTE = 8;

  int bitStrLen = sizeof(int) * BITS_PER_BYTE * sizeof(char); 

  char* p = (char*)malloc(bitStrLen);

  for (int i = (bitStrLen - 1); i >= 0; i--)
  {
    int k = 1 & num;
    *(p + i) = ((k == 1) ? '1' : '0');
    num >>= 1;
  }
  
  return p;
}

Explanation: our function takes an int as the argument and returns a char pointer which points to the bit string. Also, remember that there are 8 bits per byte, that's why we have that constant declared in the first line.

  1. Allocating memory from the heap to store our bit string: each bit is represented by a char ('0' or '1'). Thus, to get the total number of bytes required, we need the total of bits our integer has, and the number of bytes each char needs.

    To get the total number of bits each integer has, we use sizeof(int) * BITS_PER_BYTE. sizeof(int) gives the number of bytes each integer has, and BITS_PER_BYTE is the number of bits each byte has. Thus, multiplying them together, we have the total number of bits each integer has.

    To get the number of bytes each char needs, we just call sizeof(char)

    By multiplying the number of bits the integer has with the number of bytes each char needs, we get the total number of bytes required to store the binary string representation of the integer. Hence, bitStrLen = sizeof(int) * BITS_PER_BYTE * sizeof(char).

  2. Next, we explicitly allocate enough memory from the heap to store our bit string by calling the malloc function.

  3. Finally, we convert the integer into bit string using the for loop. Notice that the number of bytes we need is also the number of characters the bit string has. That's why our loop needs to run from 0 to 32 only.

    For each iteration, we check the right most bit of the integer by using bitwise manipulation: 1 & num. If the outcome is 1, then the right most bit must be 1. Otherwise, the right most bit must be 0. This works because any number with 1 at the right most bit will give the result of 1 when it AND with the number 1. But if the right most bit is 0, then the result is 0. For example, 1101 & 1 = 1 because 1101 has 1 as the right most bit.

    After converting the current right most bit, we need to shift the integer to the right one position to convert the next bit. Hence, num >>= 1

That's all we have for this post. If there is any suggestion or better solution, please leave it in the comment section below :) Thanks for reading!

1 comment:

  1. For efficiency, int k should be declared outside the for loop.
    malloc is not complemented with free - memory leak.

    ReplyDelete