Integer to Binary Using Recursion

Problem:
Get binary equivalent of a number using Recursion.
getBinary(2)       = 10
getBinary(5)       = 101
getBinary(1024) = 10000000000

Iterative implementation of this problem is quite trivial. But here it's expected to be done recursively!

Approach 1

The approach is quite simple -  Divide the decimal value by 2 and write down the remainder. Repeat this process until you can't divide anymore. 

Calculate for 13,

 13/2 = 6 and remainder = 1

 6/2   = 3 and remainder = 0

 3/2   = 1 and remainder = 1

 1/2   = 0 and remainder = 1        

To get binary, we write down the value of reminder from bottom to top. So it gives 1101. Let's apply recursive thinking to solve this problem. 

Subproblem will be dividing the number by 2 in each iteration. 

Base Case - binary of 1 is 1 (or 0 is 0) . 

Combining subproblem result might be tricky as it needs to be done in a reverse way. This can be achieved if the method is called first (and then the remainder operation is performed). This will ensure that the remainder is performed only when base case is reached.

public static String getBinary(int num) {
 if (num < 2) {
  return "" + num;
 }

 return getBinary(num / 2) + num % 2;
}

Stack Progress
getBinary(13)
    --> getBinary(13/2) + 13%2
             --> getBinary(6/2) + 6%2
                     -->getBinary(3/2) + 3%2
                             -->getBinary(1)    //base case, return 1
                     --> ""+ 1+ 1
             --> ""+1+1+0
     -->""+1+1+0+1   

Approach 2

Let's explore on another approach which uses bit manipulation to generate a binary equivalent. 

Binary of 5 is 101. Now let's see if we can get the bit values (1, 0 and 1) of the number by some bit manipulation technique. 

5 & 100 = 100   

5 & 010 = 000

5 & 001 = 001

Notice that, And operation (&) is performed with a number whose all values are 0 except leftmost position. And then that keeps on shifting to the right side. And the output will be 1 at that position if the bit value is 1 in the number (and 0 otherwise).

When you apply recursive thinking, it's quite clear that method needs another argument which will help in getting bit value at a given position. Integer in Java is 32 bit long, so that number will take the initial value of 1 << 31 (i.e. leftmost bit is 1 and rest all are 0). And when all bit positions (from MSB to LSB) are explored the recursion should stop. 

public static String getBinary2(int num, int and){
 if(and == 0){
      return "";   //if all bits are checked; just return
 }

 /**
  * If value at position is 1 in num; it will give and value
  */
 int t = (num & and) == and ? 1 : 0;
 
 return ""+ t + getBinary2(num, and >>> 1);
}

String binary = getBinary2(5, 1<<31);

//binary = 00000000000000000000000000000101

Can you try to come up with stack progress as shown for first approach?
Do post your feedback/doubts below!
---
keep coding !!!

Bit level tricks: XOR

Here goes exclusive post for Exclusive-OR / XOR !

XOR is a binary operator which acts on two number like A XOR B, denoted as A ^B.  A ^ B basically tells how different A is from B (or vice-versa). If a bit of A is different from the same bit of B, the resulting bit is 0.

Properties

1.   XOR with itself results 0

XOR-ing a number with itself returns 0. This also goes with the definition that XOR tells how different two numbers are. X ^ X = 0

     00000100   (4 in binary)                     
^   00000100   (4 in binary)
     ------------
     00000000

 

2.   XOR with 0 results number

 XOR-ing with zero gives back the same number.  X ^ 0 = X

     00000100   (4 in binary)                     
^   00000000   (0 in binary)
     ------------
     00000100

 

3.   XOR is associative and cumulative

 XOR is associative as well cumulative.

Associativity:  (X^Y)^Z = X^(Y^Z)

Cumulative:  X^Y = Y^X 

 

Bit Hacks

Let's see some XOR hacks.

#1: Swapping without temp variable

 X = X ^ Y

 Y = X ^ Y

 X = X ^ Y

Let's prove it by taking an example

X = A, Y = B

X = X ^ Y = A^ B

Y = X ^ Y = (A^B)^B = A^(B^B)  

    = A^0 //by property 1

    = A // by property 2

X = X ^ Y = (A^B)^A

    = B^(A^A)

    = B

#2: Check if two numbers have same sign

If two numbers have same sign then the MSB will be same (i.e. either both will be 0 or 1). This means that XOR of that bit will result in zero. 

 X ^ Y --> MSB of both numbers will be 0 if both numbers have same sign.

     00100100   (X)
^   01100011    (Y)
     ------------

     01000111     (>=0)

Above approach can be generalized as 

X ^ Y >= 0 

#3: Toggle between two values of a variable

Change value of a variable between two allowed values. So if the value is A change it to B and vice-versa. 

if X = A

change value of X to B 

XOR properties discussed above helps in achieving this. 

X = A ^ B ^ X

X = A ^ B ^ X

    = A ^ B ^ A   // X = A

    = (A^A)^B

    = B

 ---

keep coding !!!

Bit level tricks: setting and unsetting right most 1 bit

This post is in continuation with the earlier post, where I have discussed some of the bit manipulation techniques. In previous post, I discussed about how to set, unset and toggle a bit at fixed position like 3rd from right/LSB, 1st from left/MSB etc. Setting and unsetting a bit at fixed position is relatively easier to achieve by using left and right shift operators.
 
This post will discuss about manipulating a bit at relative positions, like right most 1 bit, left most 0th bit etc. Here also, I will explain all tricks using 8 bit number.

 

Bit Hacks

#1: Unset the rightmost 1 bit

So objective is to turn off the right most 1 bit in a number.  If input number is 10100100 then it needs to get converted into a number with b2 (b0 is LSB; highlighted bit is b2) getting turn off.

                           X    = 00100100 

                          X-1  = 00100011   

   Expected response = 00100000   ??

As shown above, subtracting 1 from number unsets the right most 1 but it also sets the zeros right to 1. Please note that other bits left of targeted 1 remain unchanged. Can X and X-1 be combined to get the expected response. If you notice closely the last 2 bits, ANDing looks to do the job. 

     00100100   (36 in binary)
&  00100011    (36 -1 )
     ------------
     00100000 

     10000000 (-128 in binary)

&  01111111  (-128 -1 in binary = 127 )

     ------------

     00000000

 

     00000000 (0 in binary; there is no right most bit)

&  11111111  (0 -1 in binary = -1)

     ------------

     00000000  (no change)

General formula for unsetting the right most 1 bit of a number, X

X = X  & (X-1)

Also, be careful of the impact of changing AND to OR in above formula.

#2: Unset all except rightmost 1 bit

So we need to unsets (clears off or changes to 0) all bits except the right most 1 bit. Trivial approach to solve this would be to RIGHT SHIFT the number until you encounter the set bit (i.e. 1) and counting the number of shifts done. 

    while(X & 1 != 0){

        count++;

        X = X>> 1;

    }

 Above approach more easier to think logically but execution complexity and verbosity is high. Let's think of abstracting it into minimal number of steps. 

     00100100   (X = 36;  in binary)
     11011011    (~X )

                +1
     ------------
     11011100  (-X; in two's complement system -X = ~X+1)

Let's use above -X 

     00100100   (X = 36;  in binary)
&  11011100  (-X)
     ------------
     00000100  (bingo!!!)

     10000000   (X = -128;  in binary)
&  10000000  (-X = -128)
     ------------
     10000000  

And it can be generalized as:

X = X  & (~X)

#3: Set the right most 0-bit

So this hack expects to turn on the right most 0 bit (irrespective of position). This also can be achieved by multiple steps but we want to achieve it compactly. 

     00100100   (X = 36;  in binary)

                +1
     ------------
     00100101  (X+1; )

So adding 1 sets up the right most 0. This can be used to set the right most 0 to 1. 

      00100100   (X = 36;  in binary)

  |   00100101   (X+1 )
     ------------
      00100101  

      01110111   (X )

  |   01111000   (X+1 )
     ------------
      01111111

So OR-ing X with X+1 does the job. 

X = X  | (X+1) 

Related Post : Bit manipulation in Java

 Bit level tricks : setting, unsetting and toggling a bit

----

keep coding ! 

Bit Vector

The bit vector is also referred to as bit-array or bit-set. As the name suggests, it's array of bits. Every modern programming language supports primitive or basic data types like byte, integer, short etc which are inherently array of bits only. So, is bit-array different? 

A byte is composed of 8-bits. Literally, byte data type is also a bit-array of 8 bits or 1 byte.  Integer data type of 4 bytes is a bit-array of 32 bits and so on. This is where the similarity stops and life of bit-array begins. 

To understand it further let's take an example. Assume that you want to represent a set of integers in the range of 0 and 999 (both are inclusive). An option which you have as a programmer is; store these integers in an array of length 1000 or a list which can grow up to 1000. Remember, it's a set, so you are going to store only unique numbers in the range. 

//Java snippet

int[] set = new int[1000];

set[i] = num

What is the memory requirement of above?

Each integer takes 4 bytes. So total memory requirement for 1000 integers is 4KB (=4*1000 byte).  

can we improve? 

If the requirement says that not all numbers in the range might be present in the set, we can use ArrayList instead of an array. So this will improve a bit, as the numbers which are not in the set will not occupy any memory. This helps to an extent but worst-case memory requirement is still 4KB. 

can we improve?

As long as you going to store each element of the set in an integer, space overhead is going to remain the same.

Bit-Array

A bit can only take two values i.e. 0 or 1.  It can be used to denote the presence or absence of an item. So as discussed above, a byte is an array of 8 bits. This means these 8 bits can be used to represent presence/absence of an item in the set. Recall that in an integer array, the index is used to get element stored at that location. Similarly, in bit-set, bit at a position can be used to represent the presence of a number.

So as shown in the above figure, we can represent a set of integers in the range of 0 and 7, can be represented by just 1 byte ( or 8 bits). If the number is present make bit at the corresponding bit as 1. 

So below two operations can be performed on bit-set.

1. Setting an integer in the array
2. Testing if an integer exists in the array/set

Implementing Bit-vector

Now, let's return to our initial problem of storing integers in the range of 0 and 999. 

Number of bits required = 1000

Number of bytes required = 1000/8 = 125

So 1000 integers can be represented in 125 bytes.

Below is the Java implementation:

/**
 * Bit-vector to store integers
 * 
 * @author Siddheshwar
 * 
 */
public class BitArray {
 private byte[] set;

 public BitArray(int length) {
  int arraysize = length >> 3;

  // if length is not multiple of 8
  if (length % 8 != 0) {
   arraysize++;
  }
  this.set = new byte[arraysize];
 }

 /**
  * Set given number in the bit-array i.e. make corresponding bit as 1
  * 
  * @param number
  */
 public void storeNumber(int number) {
  if (number > (set.length << 3) || number < 0) {
   throw new IllegalArgumentException("number out of range");
  }

  int arrayIndex = this.getArrayIndex(number);
  int bitIndex = this.getBitIndex(number);

  // shift 1 to the bit index
  int pos = 1 << bitIndex;

  // so bit at position needs to be made 1
  this.set[arrayIndex] = (byte) (this.set[arrayIndex] | pos);
 }

 /**
  * Check if the number exists in the array if the corresponding bit is 1
  * then number exists
  * 
  * @param number
  */
 public boolean numberExists(int number) {
  if (number > (set.length << 3) || number < 0) {
   throw new IllegalArgumentException("number out of range");
  }

  int arrayIndex = this.getArrayIndex(number);
  int bitIndex = this.getBitIndex(number);

  // shift 1 to the bit index
  int pos = 1 << bitIndex;

  // check bit at position is 0 or 1
  return (this.set[arrayIndex] & pos) > 0 ? true : false;
 }

 private int getArrayIndex(int number) {
  return number >> 3; // divide by 8
 }

 private int getBitIndex(int number) {
  return number % (1 << 3); // % 8
 }

 private void printSet() {
  System.out.println("\n array content :");
  for (int i = 0; i < set.length; i++)
   System.out.print(Integer.toBinaryString(this.set[i]));
 }

 //test method
 public static void main(String[] args) {
  BitArray array = new BitArray(1000);
  System.out.println("length of array :" + array.set.length);

  int num1 = 17;
  array.storeNumber(num1);

  int num2 = 171;
  array.storeNumber(num2);

  int num3 = 400;
  array.storeNumber(num3);

  System.out.println("val " + num1 + " exists ? "
    + array.numberExists(num1));
  System.out.println("val " + num2 + " exists ? "
    + array.numberExists(num2));
  System.out.println("val " + num3 + " exists ? "
    + array.numberExists(num3));
  System.out.println("val " + 500 + " exists ? "
    + array.numberExists(500));

  for (int i = 0; i < 1000; i = i + 2)
   array.storeNumber(i);

  array.printSet();

  /*
   * for(int i = 0; i< 1000; i++) System.out.println(array.get(i));
   */
 }
}

Output:
length of array :125
val 17 exists ? true
val 171 exists ? true
val 400 exists ? true
val 500 exists ? false

 array content :
10101011010101101011110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110111011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101101010110101011010101

---
keep coding !!!

Bit Manipulation in Java

Java inherited bit manipulation from C. As a programmer you might not use it often, but still, it's quite important. Java integers are of 32 bits (4 bytes) and are signed. This means that left most bit (Most Significant Bit / MSB) works as the sign identifier. If it's 1, the number is negative (and positive if it's 0). Let's go in detail on the binary form of numbers:

Binary Representation of Numbers

Integer 1 in binary form  = 00000000000000000000000000000001  or 1

Integer -1 in binary form =11111111111111111111111111111111

In Java, you can get the binary representation of any number by calling toBinaryString() method of Integer class (Integer.toBinaryString(1)). The binary representation of -1 might be confusing if you are not aware of how negative numbers gets stored. Negative numbers get stored as two's complement which can be achieved by adding 1 to the NOT of the unsigned number i.e. ~number +1

Another way to look at it is, the weight of the MSB or leftmost bit is negative. So when this bit is 1, the number becomes negative. The binary form of -1 can be represented as:
   -2^31*1+ 2^30*1 + 2^29*1 + 2^28*1+ .... ......+ 2^1*1+2^0*1

Note that, the highest weighted component is negative (-2^31*1). This will result in the overall number being negative. We can cross check it by assuming a 4-bit number system.

1111 = -2^3*1 + 2^2*1 + 2^1*1 + 2^0*1
         = -8 +4 + 2 +1
         = -1

Using two's complement technique, -1 = ~1 +1
       -1 = ~1+1
          =  ~0001 + 1
          =   1110 + 1
          =   1111      

So either way, you will get the same representation of a negative number.

Bitwise Operators

We have used NOT binary operator above, now it's time to go over Java binary operators in detail. 

~ (NOT)
Flips or reverses all bits. Thus, every 1 becomes 0 and every 0 becomes 1. Also known as one's complement operator. It's a urinary operator so takes only one argument.
~101 produces 010

| (OR)
Produces one in output if at least one of the bit is 1 and produces 0 if both bits are 0.
101 | 10 produces 111

& (AND)
Produces 1 in output if both input bits are 1, otherwise, it results in 0.
101 & 10 produces 000

^ (EXCLUSIVE OR / XOR)
Produces 1 in the output if either of the bit is 1 (not both), otherwise 0
101 ^ 10 produces 111
2 ^ 10 produces 8  ( equivalent to 10 ^ 1010 )

Important Note

• Difference between bitwise operators (&, |) with logical operators && and ||. Bit operators take integers and results in other integers but logical operators take booleans and return a boolean result.
• Only NOT (~) is urinary, others are binary operators. 
• Binary operators (i.e. | , & and ^) can be combined with the = sign like &=, |= and ^=

Shift Operators

Now let's go to the Java's powerful shift operators. 

<< (Left Shift Operator)

Used for shifting bits of a number on left side (i.e. 8 << 1 or 00001000 << 1). The value to the right of the operator indicates how many positions to shift the bits. Bits that fall off on the left side are lost and empty bits on the right side are filled up with 0. 

Note, the value can change sign depending on the state of first bit. 

>> (Signed Right Shift Operator)

Used for shifting bits of a number on the right side ( 8 >> 1). The value to the right of the operator indicates how many positions to shift the bits. 

• When the sign is positive (leftmost bit is 0),  empty bits on left side fills up with 0. So it retains the sign. 
• When the sign is negative (leftmost bit is 1), it performs sign extension. Fills up the empty bits on the left side with 1s. 

>>> (Unsigned Right Shift Operator)

Regardless of the sign, zeros are inserted to the left side or higher order bits.

Let's take a simple example to illustrate above operators

 public class BinaryOperators {  
      public static void main(String[] args) {  
           int i = 17;  
           System.out.println(" i :" + Integer.toBinaryString(i));  
           System.out.println(" ~i : " + Integer.toBinaryString(~i));  
           System.out.println(" -1 : " + Integer.toBinaryString(-1));  
           System.out.println(" -1 & i : " + Integer.toBinaryString(-1 & i));  
           System.out.println(" -1 ^ i : " + Integer.toBinaryString(-1 & i));  
           System.out.println(" i >> 2 : " + Integer.toBinaryString(i >> 2));  
           System.out.println(" i >>> 2 : " + Integer.toBinaryString(i >>> 2));  
           System.out.println(" i << 2 : " + Integer.toBinaryString(i << 2));  
           System.out.println(" -1 >> 2 : " + Integer.toBinaryString(-1 >> 2));  
           System.out.println(" -1 >>> 2 : " + Integer.toBinaryString(-1 >>> 2));  
           System.out.println(" -i >>>= 2 : " + Integer.toBinaryString(i >>>= 2));  
      }  
 }  

Output:
 i :10001
 ~i : 11111111111111111111111111101110
 -1 : 11111111111111111111111111111111
 -1 & i : 10001
 -1 ^ i : 10001
 i >> 2 : 100
 i >>> 2 : 100
 i << 2 : 1000100
 -1 >> 2 : 11111111111111111111111111111111
 -1 >>> 2 : 111111111111111111111111111111
 -i >>>= 2 : 100

Important Observations: 

• Multiplication and Division:

      Shift operators can be used to multiply or divide a number. So if there is a need to multiply or divide a number by multiple of 2; you should prefer shift operators as it's more efficient. 

          int i = 5;

          i <<= 2 ;    //value of i becomes 20 i.e. 5*2*2

          i = 10;

          i >>=2;   // value of i becomes 2 i.e. 10/(2*2) = 2

          i = -4

          i >>=2 ;   // value of i becomes -1

• Finding bit at a position:

           If you & a bit with 1; you will get the same bit.

           i.e. 0 & 1 = 0 ; 1&1 = 1

           This can be used to get the bit value in a number at the given position. 

           

           5 & 1 = 1   // 1001 & 1 

           5 &  10  = 0 // 1001 & 10; second last bit is 0 so the output is 0

     

References:

http://sol.gfxile.net/boolean.html
http://graphics.stanford.edu/~seander/bithacks.html

----
that's it for now...do post your feedback about this post.