Number Conversion -1 : Decimal to Binary

At first glance, we think about the below algorithm
1. take input x
2. r[i] = x%2;
3. x = x/2
4. do above steps until x =0

the complexity of this algorithm is O(lgn) , where n = decimal number.



Code

---

#include<cstdio>
using namespace std;

int main(){
  int x,i;
  bool r[32]={0}; // think about 32 bits number

  printf("Enter a decimal Number: ");
  scanf("%d",&x);
  i = 0;
  while(x){
     r[++i] = x%2;
     x =x/2;
  }

  printf("Result: ");
  while(i){
     printf("%d",r[i--]);
  }

  return 0;
}

---

Now, we can replace the % and / sign by bitwise operator. How?
x = 1011
Objective: take last one bit into r[i]
x = 1011
      0001
-------------
AND      1 --- > r[i]
x = 1011
just make a right shift, we get
x = (101)

code

---

#include<cstdio>
using namespace std;

int main(){
  int x,i;
  bool r[32]={0}; // think about 32 bits number

  printf("Enter a decimal Number: ");
  scanf("%d",&x);
  i = 0;
  while(x){
     r[++i] = x&1;
     x =x>>1;
  }

  printf("Result: ");
  while(i){
     printf("%d",r[i--]);
  }

  return 0;
}

---

Although the complexity of this algorithm is O(lgn).

Would we reduce this complexity into O(1)!!!!!! Yes. We can reverse the bits of a number in O(1) if we know the size of the number. We can implement it using look up table.

Code:

---

#include<stdio.h>

int main(){
  int x=0,tx,c,flag;

  printf("Enter a number : ");
  scanf("%d",&x);

  x = ((x&0xAAAAAAAA) >> 1)| ((x& 0x55555555)<<1);
  x = ((x&0xCCCCCCCC) >> 2)| ((x& 0x33333333)<<2);
  x = ((x&0xF0F0F0F0) >> 4) | ((x& 0x0F0F0F0F)<<4);
  x = ((x&0xFF00FF00) >> 8) | ((x& 0x00FF00FF)<<8);
  x = x >> 16 | x<< 16;

  printf("Result: ");
  tx = x;
  c = 32;
  flag = 1;
  while(c--){
     if (flag ==0) {
        if (tx&1) printf("1");
        else printf("0");
     }
     else{
         if (tx&1){
             flag = 0;
             printf("1");
         }
     }
     tx = tx>>1;
  }

  return 0;
}

---

Now your task is to use paper and pencil to analysis this code.