Tuesday, January 5, 2010

Convert integer into a binary number

This code will print the binary number for the integer num:
void generatebits(int num)
{
int temp;
  if(num!=0)
  {
    temp = num % 2;
    generatebits(num >>= 1);
    printf("%d",temp);
  }
}

int main()
{
  int num;
  printf("\nEnter a number\n");
  scanf("%d", &num);
  printf("\n\n");
  generatebits(num);
  return(0);
}



Writing a function to convert integer to bits-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.

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.

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

By the way java's Integer class has a static method called toBinaryString() which converts integer to binary string.

0 comments:

Post a Comment