Name | Description |
---|---|

~a (NOT) | Negates each bit. 0s becomes 1s and vice versa. ~a=(-a)-1 |

a & b (AND) | In each pair of corresponding bits, the result is 1 if the first bit is 1 AND the second bit is 1, 0 otherwise. |

a | b (OR) | In each pair of corresponding bits, the result is 1 if the first bit is 1 OR the second bit is 1 OR both bits are 1, and otherwise the result is 0 |

a ^ b (XOR) | In each pair of corresponding bits, the result in each position is 1 if the two bits are different, and 0 if they are the same. |

a << n (LEFT-SHIFT) | Shifts bit pattern to the left by n positions and places 0s on the right. |

a >> n (RIGHT-SHIFT) | Shifts bit pattern to the right by n positions and places the sign-bit on the left, thus preserving the sign of the operand. |

a >>> n (UNSIGNED-RIGHT-SHIFT) | Shifts bit pattern to the right by n positions and places 0s on the left. |

a = 3 (11) b = 6 (110) ~a = -4 (11111111111111111111111111111100) a & b = 2 (10) a | b = 7 (111) a ^ b = 5 (101) a << 2 = 12 (1100) b >> 1 = 3 (11) b >>> 1 = 3 (11)The code used to generate this is shown below:

final int a = 3; // 011 final int b = 6; // 110 System.out.printf("a = %s\t(%s)\n", a, Integer.toBinaryString(a)); System.out.printf("b = %s\t(%s)\n", b, Integer.toBinaryString(b)); /** * NOT */ int not = ~a; System.out.printf("~a = %s\t(%s)\n", not, Integer.toBinaryString(not)); /** * AND */ int and = a & b; // 011 // 110 //----& // 010 System.out.printf("a & b = %s\t(%s)\n", and, Integer.toBinaryString(and)); /** * OR */ int or = a | b ; // 011 // 110 //----| // 111 System.out.printf("a | b = %s\t(%s)\n", or, Integer.toBinaryString(or)); /** * XOR */ int xor = a ^ b ; // 011 // 110 //----^ // 101 System.out.printf("a ^ b = %s\t(%s)\n", xor, Integer.toBinaryString(xor)); /** * LEFT-SHIFT */ int lshift = a << 2; // 00011 // ----- <<2 // 01100 System.out.printf("a << 2 = %s\t(%s)\n", lshift, Integer.toBinaryString(lshift)); /** * RIGHT-SHIFT */ int rshift = b >> 1; // 110 // ----- >>1 // 011 System.out.printf("b >> 1 = %s\t(%s)\n", rshift, Integer.toBinaryString(rshift)); /** * UNSIGNED-RIGHT-SHIFT */ int urshift = b >>> 1; // 110 // ----- >>1 // 011 System.out.printf("b >>> 1 = %s\t(%s)\n", urshift, Integer.toBinaryString(urshift));

**Usage of bit manipulation:**

So, where do you use this? In the olden days, they were used for efficiency but most modern compilers today perform optimisations for you, so you don't have to worry about it. The bitwise and bit shift operators are not used very frequently in day-to-day programming, but here are a few scenarios where they can be used - mainly to impress you colleagues :)

**1. Checking if an integer is even or odd**

If an integer is odd, its rightmost bit will always be 1 and if it is even, it will always be 0. For example, 4 is 100 and 5 is 101.

public boolean isEven(int a){ return a & 1 == 0; }

**2. Multiplying/Dividing by powers of two**

Shifting to the left is just like multiplying by a power of two. For example

`3 << 2`

is `12`

. In general, `a << n`

is `a*(2^n)`

. Keep in mind that a left shift can result in "overflow" which occurs when you exceed the limits of the range of the data type you are using and can cause unexpected behaviour.
A right shift is an integer division by a power of 2. Shifting right 1 position is the same as dividing by two. This approach is used in the Collections Framework, such as the `Arrays`

class to find the middle element of an array. In general, `a >> n`

is `a/(2^n)`

. Be careful, when right shifting negative integers. For example, `5 >> 1`

gives `2`

, but `-5 >> 1`

, gives `-3`

.

**3. Is an integer positive or negative?**

Shift the integer right 31 places. The value of the far left bit is copied to the other bits. The far left bit is 1 when the value is negative and 0 otherwise.

public boolean isNegative(int a){ return (a >> 31) != 0; }

**4. Negating an integer**

You can use the NOT operator to determine the negative of any integer as shown in the snippet below. The basic idea is you invert all the bits and then add 1.

int num = 4; int neg = ~num + 1; //-4Note that you can also do the reverse and determine the positive of a negative integer by subtracting 1 and then inverting the bits.

**5. Check if the nth bit is set**

This is a more generalised version of the even/odd check. We move the 1 bit n places to the left and then apply the AND operation. If the nth bit was not set, this would result in 0.

public boolean isBitSet(int a, int n){ return a & (1 << n) != 0; }

**6. Setting the nth bit**

a | (1<<n)

**7. Unsetting the nth bit**

a & ~(1<<n)

**8. Toggling the nth bit**

a ^ (1<<n)

**9. Unsetting the rightmost 1-bit**

a & (a-1)

**10. Checking if number is a power of 2**

If the number is a power of 2, there will be only one 1-bit. If we unset this bit, we will get 0.

return (a & (a-1)) == 0;

**11. Swapping values without a temporary variable**

Swap two variables without a temporary variable using XOR:

x = x ^ y; y = x ^ y; x = x ^ y;

**References:**

Bit Twiddling Hacks

Java Ranch - Bit Shifting

Low Level Bit Hacks You Absolutely Must Know

This is an extremely helpful refresher. Thanks!

ReplyDeletethe swapping trick is very cool!

ReplyDeleteyour unsigned right shift operator is wrong. I think you meant '>>>'

ReplyDeleteThanks, you're right. It was a typo. I have fixed it now.

ReplyDelete