Google

Jul 14, 2014

Java bitwise operators with practical examples

Even though there is rarely a time bitwise operations seem directly necessary, the standard Java libraries use bitwise operations indirectly for efficient processing. For example, the StringBuffer.reverse( ), Integer.toString( ), BigDecimal and BigInteger classes to name a few. There are number of practical examples listed where bitwise operations are very handy. Some interviewers prefer asking questions on this topic or including it in the written test to determine how technical you are.


Example 1: To pack and unpack values. For example, to represent
  • age of a person in the range of 0 to 127. Use 7 bits.
  • gender of a person 0 or 1 (0 – female and 1 – male). Use 1 bit.
  • height of a person in the range of 0 to 255. Use 8 bits.

To pack this info: (((age << 1) | gender ) << 8 ) | height. For example, age = 25, gender = 1, and height = 255cm. Shift the age by 1 bit, and combine it with gender, and then shift the age and gender by 8 bits and combine it with the height.

Packing

Age
Gender
Height
Bits
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
age (25 years) using 7 bits
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
Age << 1 (Shift age by 1 bit)
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
Gender (1 – male) using 1 bit
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
Combine age with gender:

(age << 1) | gender
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
((age << 1) | gender ) << 8 ), shift age and gender by 8 bits.
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
0
Height (255 cm) using 8 bits.
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
Combine height with age and gender:

val = (((age << 1) | gender ) << 8 ) | height
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1

Age range

16 + 8 + 1 = 25
Gender
= 1
Height range

128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255.


public class Binary5 {

    public static void main(String[ ] args) {
        
        //packing
        int val = ((((25 << 1) | 1) << 8) | 255);
        System.out.println("packed=" + val);
        System.out.println("packed binary=" 
                               + Integer.toBinaryString(val));       //0011001111111111
        
        //unpacking
        System.out.println("height=" + (val & 0xff));                //extract last 8 bits.
        System.out.println("gender=" + ((val >>> 8) & 1));  //extract bit 9
        System.out.println("age=" + ((val >>> 9)));         //extract bits 10 – 16.

    }
}

Output: 

packed=13311
packed binary=11001111111111
height=255
gender=1
age=25


Unpacking (or extracting) height: Extract the low order 8 bits.
packed value:
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
Masking: 0xFF
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
Extract height =
value & 0xFF:
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1









27
26
25
24 23 22 21 20
height:








128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255



Unpacking (or extracting) gender: Extract bit 9.
packed value:
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
8 lower order bits (i.e. shaded area) are shifted out.

value >>> 8
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
Masking: 1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
Extract gender =
(value >>> 8) &1:
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
















20
gender:















1

Unpacking (or extracting) age: Extract bits 10 – 16 (i.e. higher order bits ).

packed value:
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
Extract age =
value >>> 9:
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1










26
25 24 23 22 21 20
age:









24 + 23 + 20 = 16 + 8 + 1 = 25



Example 2: To compactly represent a number of attributes like being bold, italics, etc of a character in a text editor. This is a more practical example.


shadow
blink
subscript
superscript
strikethrough
underline
italics
bold
0
1
0
1
0
0
0
1


import java.util.Arrays;

public class Binary6 {
    public static void main(String[ ] args) {
        byte[ ] vals = { 0, 1, 0, 1, 0, 0, 0, 1 };

        byte value = pack(vals);
        System.out.println("packedValue=" + value);    // 81
        System.out.println("unpackedValues="
                + Arrays.toString(unpack(value)));     // [0, 1, 0, 1, 0, 0, 0, 1]
    }

    public static byte pack(byte[ ] vals) {
        byte result = 0;
        for (byte bit : vals) {
            result = (byte) ((result << 1) | (bit & 1));
        }
        return result;
    }

    public static byte[ ] unpack(byte val) {
        byte[ ] result = new byte[8];
        for (int i = 0; i < 8; i++) {
            result[i] = (byte) ((val >> (7 - i)) & 1);
        }
        return result;
    }
}



Example 3: If you can think of anything as slots or switches that need to be flagged on or off, you can think of bitwise operators. For example, if you want to mark some events on a calendar. 

6
Saturday
5
Friday
4
Thursday
3
Wednesday
2
Tuesday
1
Monday
0
Sunday















 
Example 4: To multiply or divide by 2n.
 
public class ShiftOperator {
    
    //multiply by 2 power n. n = 6
    private static final int  MULTIPLY = 10 << 6;
    //Divide by  2 power n where n = 6.
    private static final int  DIVIDE = 640 >> 6;
    
    public static void main(String[ ] args) {
         System.out.println(MULTIPLY);               // 640
         System.out.println(DIVIDE);                 // 10
    }
} 

Labels:

0 Comments:

Post a Comment

Subscribe to Post Comments [Atom]

<< Home