Bitwise Operations are an important tool for optimizing performance, improving code readability, and reducing code complexity in Java applications.
The advantages of using Bitwise Operations are :
- Speed Optimization : Bitwise operations are much faster than arithmetic operations as they operate directly on binary representations of numbers;
- Space Optimization : Bitwise operations can be used to store multiple values in a single variable, which can be useful when working with limited memory;
- Code Simplification : Bitwise operations can simplify the code by reducing the number of conditional statements and loops required to perform certain tasks.
What You Need
- About 16 minutes
- A favorite text editor or IDE
- Java 8 or later
- 1. Bit Literals
- 2. Bitwise Operators
- 3. Bit Shift Operators
- 4. Bit Operations Examples
- 4.1 Print Binary Value Of Integral Type
- 4.2 Difference between bitwise and logical AND/OR
- 4.3 Use bitwise NOT to get the opposite of a number
- 4.4 Use bitwise XOR to swap the values of two number
- 4.5 Use bit operations to find out the max of two values
- 4.6 Find the only number occurring odd number of times in an array
- 4.7 Find the only two numbers occurring odd number of times in an array
- 4.8 Check a number is power of 2
- 4.9 Arithmetic operations using bit operations
- 4.10 Multiply or Divide a positive number by 2^n using bit shift operators
- 4.11 BitSet
- 4.12 Set or unset the given bit position of an integer
1. Bit Literals
In Java, we can represent integral types such as byte, short, int and long as :
- binary numbers : using the form 0b (or 0B) followed by one or more binary digits (0 or 1);
- octal numbers : using a leading 0 (zero) digit and one or more additional octal digits (digits between 0 and 7);
- hexadecimal numbers : using the form 0x (or 0X) followed by one or more hexadecimal digits (digits from 0 to 9, a to f or A to F).
public claass BitOperationsTest1 {
public static void main(String[] args) {
// binary representation of 9
int a = 0b00000000000000000000000000001001;
System.out.println(a);
// octal representation of 9
int b = 000000000011;
System.out.println(b);
// hexadecimal representation of 9
int c = 0x00000009;
System.out.println(c);
// binary representation of -9
int aa = 0b11111111111111111111111111110111;
System.out.println(aa);
// octal representation of -9
int bb = 037777777767;
System.out.println(bb);
// hexadecimal representation of -9
int cc = 0xFFFFFFF7;
System.out.println(cc);
}
}
The output of above code snippet is below :
9
9
9
-9
-9
-9
Tips : How to convert negative decimal value to binary value ?
Let us take an example of converting -9, to get its binary value, we can proceed below steps :
- convert 9 to binary value:
- 9
- =>
- 00000000000000000000000000001001
- subtract 1 :
- 00000000000000000000000000001001
- =>
- 00000000000000000000000000001000
- apply NOT :
- 00000000000000000000000000001000
- =>
- 11111111111111111111111111110111
After above 3 steps, we get 11111111111111111111111111110111, it is the binary value of -9.
And vice versa ? How to convert negative binary value to decimal value ?
For instance, we need to convert 11111111111111111111111111110111 to its decimal value.
We can proceed below steps :
- apply NOT :
- 11111111111111111111111111110111
- =>
- 00000000000000000000000000001000
- add 1 :
- 00000000000000000000000000001000
- =>
- 00000000000000000000000000001001
- convert to decimal value :
- 00000000000000000000000000001001
- =>
- 9
We know that the first bit of original binary value is 1, so it must be a negative decimal number.
So we get -9 in the end, it is the decimal value of 11111111111111111111111111110111.
2. Bitwise Operators
Bitwise operators are used to perform the manipulation of individual bits of a number.
They can be used with any integral type (char, short, int, etc).
2.1 Bitwise AND (&)
If both bits are 1, it gives 1, else it shows 0.
a = 5 = 0101 (In Binary)
b = 7 = 0111 (In Binary)
a & b = 0101 & 0111 = 0101 = 5 (In decimal)
2.2 Bitwise OR (|)
If either of the bits is 1, it gives 1, else it shows 0.
a = 5 = 0101 (In Binary)
b = 7 = 0111 (In Binary)
a | b = 0101 | 0111 = 0111 = 7 (In decimal)
2.3 Bitwise XOR (^)
If corresponding bits are different, it gives 1, else it shows 0.
a = 5 = 0101 (In Binary)
b = 7 = 0111 (In Binary)
a ^ b = 0101 ^ 0111 = 0010 = 2 (In decimal)
2.4 Bitwise NOT (~)
It inverts all bits, which means it makes every 0 to 1, and every 1 to 0.
a = 5 = 0101 (In Binary)
~ a = ~ 0101 = 1010 = 10 (In decimal)
3. Bit Shift Operators
Shift operators are used to shift the bits of a number left or right.
3.1 Left Shift (<<)
The left shift operator shifts the bits to the left by the number of times specified by the right side of the operand.
After the left shift, the empty space in the right is filled with 0.
a = 5 = 0101 (In Binary)
a << 2 = 0100 = 4 (In decimal)
3.2 Right Shift (>>)
The right shift operator shifts all the bits to the right.
When an input number is negative, where the leftmost bit is 1, then the empty spaces will be filled with 1.
When an input number is positive, where the leftmost bit is 0, then the empty spaces will be filled with 0.
a = 5 = 0101 (In Binary)
a >> 2 = 0001 = 1 (In decimal)
a = -5 = 11111111111111111111111111111011 (In Binary)
a >> 2 = 11111111111111111111111111111110 = -2 (In decimal)
3.3 Bitwise Zero Fill Right Shift (>>>)
It is also called Unsigned Right Shift.
This operator is very similar to the right shift operator.
The only difference is that the empty spaces in the left are filled with 0 irrespective of whether the number is positive or negative.
a = 5 = 0101 (In Binary)
a >>> 2 = 0001 = 1 (In decimal)
a = -5 = 11111111111111111111111111111011 (In Binary)
a >>> 2 = 00111111111111111111111111111110 = 1073741822 (In decimal)
4. Bit Operations Examples
4.1 Print Binary Value Of Integral Type
In below code snippet, we print the binary value of an int (32 bits).
public class BitOperationsTest5 {
public static void main(String[] args) {
int a = 9;
printBinary(a);
int b = -9;
printBinary(b);
int c = 0b00000000000000000000000000001001;
printBinary(c);
int d = 0b11111111111111111111111111110111;
printBinary(d);
}
private static void printBinary(int num) {
for (int i = 31; i >= 0; i--) {
int mask = 1 << i;
if ((num & mask) == 0) {
System.out.print("0");
} else {
System.out.print("1");
}
}
System.out.println();
}
}
The output of above code snippet is below :
00000000000000000000000000001001
11111111111111111111111111110111
00000000000000000000000000001001
11111111111111111111111111110111
The same can be done for printing the binary value of a long (64 bits).
public class BitOperationsTest6 {
public static void main(String[] args) {
long a = 9L;
printBinary(a);
long b = -9L;
printBinary(b);
long c = 0b0000000000000000000000000000000000000000000000000000000000001001L;
printBinary(c);
long d = 0b1111111111111111111111111111111111111111111111111111111111110111L;
printBinary(d);
}
private static void printBinary(long num) {
for (int i = 63; i >= 0; i--) {
long mask = 1L << i;
if ((num & mask) == 0L) {
System.out.print("0");
} else {
System.out.print("1");
}
}
System.out.println();
}
}
Below is the output of above code snippet :
00000000000000000000000000001001
11111111111111111111111111110111
00000000000000000000000000001001
11111111111111111111111111110111
4.2 Difference between bitwise and logical AND/OR
The logical AND operator && does not evaluate the second operand if the first operand becomes false.
Similarly the logical OR operator || does not evaluate the second operand when first operand becomes true.
But the bitwise AND & and bitwise OR | operators always evaluate their operands.
public class BitOperationsTest3 {
public static void main(String[] args) {
System.out.println(returnFalse() & returnTrue());
System.out.println();
System.out.println(returnFalse() && returnTrue());
System.out.println();
System.out.println(returnTrue() | returnFalse());
System.out.println();
System.out.println(returnTrue() || returnFalse());
}
private static boolean returnTrue() {
System.out.println("Inside returnTrue method");
return true;
}
private static boolean returnFalse() {
System.out.println("Inside returnFalse method");
return false;
}
}
The output of above code snippet is below :
Inside returnFalse method
Inside returnTrue method
false
Inside returnFalse method
false
Inside returnTrue method
Inside returnFalse method
true
Inside returnTrue method
true
4.3 Use bitwise NOT to get the opposite of a number
The opposite of number a is -a, we can also get it by ~a + 1.
Pay attention to the fact that in Java, there is no way to get the opposite of the minimum number.
public class BitOperationsTest2 {
public static void main(String[] args) {
int a = 2;
System.out.println(a);
int aa = -a;
System.out.println(aa);
int aaa = ~a + 1;
System.out.println(aaa);
int b = Integer.MIN_VALUE;
System.out.println(b);
int bb = -b;
System.out.println(bb);
int bbb = ~b + 1;
System.out.println(bbb);
}
}
Below is the output of above code snippet :
2
-2
-2
-2147483648
-2147483648
-2147483648
4.4 Use bitwise XOR to swap the values of two number
Bitwise XOR operator ^ can be used when swapping the values of two number.
Because bitwise XOR operator has below characteristics :
a ^ a = 0
a ^ 0 = a
a ^ 1 = ~a
public class BitOperationsTest7 {
public static void main(String[] args) {
int a = 10;
int b = 9;
System.out.println("a = " + a);
System.out.println("b = " + b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("a = " + a);
System.out.println("b = " + b);
}
}
The output of above code snippet is below :
a = 10
b = 9
a = 9
b = 10
Pay attention to the fact that it would not work when swapping the value of a number itself.
public class BitOperationsTest8 {
public static void main(String[] args) {
int[] arr = {10, 9};
System.out.println("arr[0] = " + arr[0]);
System.out.println("arr[1] = " + arr[1]);
swap(arr, 0, 1);
System.out.println("arr[0] = " + arr[0]);
System.out.println("arr[1] = " + arr[1]);
swap(arr, 0, 0);
System.out.println("arr[0] = " + arr[0]);
System.out.println("arr[1] = " + arr[1]);
}
private static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
Below is the output of above code snippet :
arr[0] = 10
arr[1] = 9
arr[0] = 9
arr[1] = 10
arr[0] = 0
arr[1] = 10
As you can see that the swap for the first element itself is not working in above code snippet.
In this case, it can be fixed by adding a check of the same element before swapping the values :
public class BitOperationsTest21 {
public static void main(String[] args) {
int[] arr = { 10, 9 };
System.out.println("arr[0] = " + arr[0]);
System.out.println("arr[1] = " + arr[1]);
swap(arr, 0, 1);
System.out.println("arr[0] = " + arr[0]);
System.out.println("arr[1] = " + arr[1]);
swap(arr, 0, 0);
System.out.println("arr[0] = " + arr[0]);
System.out.println("arr[1] = " + arr[1]);
}
private static void swap(int[] arr, int i, int j) {
if (i != j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
}
Below is the output of above code snippet :
arr[0] = 10
arr[1] = 9
arr[0] = 9
arr[1] = 10
arr[0] = 9
arr[1] = 10
4.5 Use bit operations to find out the max of two values
Without using any comparison operators, it is possible to find out the max of two values by using bit operations.
But pay attention to the fact that in below code snippet, it is not able to handle the case of int value overflow.
public class BitOperationsTest10 {
public static void main(String[] args) {
System.out.println(maximum(10, 11));
System.out.println(maximum(10, -11));
System.out.println(maximum(-10, 11));
System.out.println(maximum(-10, -11));
System.out.println();
System.out.println(maximum(Integer.MAX_VALUE, Integer.MIN_VALUE));
System.out.println(maximum(Integer.MIN_VALUE, Integer.MAX_VALUE));
}
private static int maximum(int a, int b) {
int c = a - b;
int sc = sign(c);
return flip(sc) * a + sc * b;
}
private static int sign(int i) {
return i >>> 31;
}
private static int flip(int i) {
return i ^ 1;
}
}
The output of above code snippet is below :
11
10
11
-10
-2147483648
-2147483648
As you can see that in above code snippet, when we try to compare the minimum value with the maximum value, the result is not correct because of the overflow.
Below code snippet is an advanced version being able to handle the overflow issue.
public class BitOperationsTest11 {
public static void main(String[] args) {
System.out.println(maximum(10, 11));
System.out.println(maximum(10, -11));
System.out.println(maximum(-10, 11));
System.out.println(maximum(-10, -11));
System.out.println();
System.out.println(maximum(Integer.MAX_VALUE, Integer.MIN_VALUE));
System.out.println(maximum(Integer.MIN_VALUE, Integer.MAX_VALUE));
}
private static int maximum(int a, int b) {
int c = a - b;
int sa = sign(a);
int sb = sign(b);
int diff = sa ^ sb;
int same = flip(diff);
int sc = sign(c);
return diff * flip(sa) * a + diff * flip(sb) * b + same * (flip(sc) * a + sc * b);
}
private static int sign(int i) {
return i >>> 31;
}
private static int flip(int i) {
return i ^ 1;
}
}
Below is the output of above code snippet :
11
10
11
-10
2147483647
2147483647
4.6 Find the only number occurring odd number of times in an array
public class BitOperationsTest12 {
public static void main(String[] args) {
int[] arr = { 1, 1, 2, 2, 3, 4, 4, 5, 5 };
int odd = 0;
for (int i = 0; i < arr.length; i++) {
odd ^= arr[i];
}
System.out.println("The only number occurring odd number of times in the array is " + odd);
}
}
The output of above code snippet is below :
The only number occurring odd number of times in the array is 3
4.7 Find the only two numbers occurring odd number of times in an array
public class BitOperationsTest14 {
public static void main(String[] args) {
int[] arr = { 1, 1, 2, 2, 3, 4, 4, 5 };
int odds = 0;
for (int i = 0; i < arr.length; i++) {
odds ^= arr[i];
}
int mask = oneAtTheMostRightSide(odds);
int firstOdd = 0;
for (int i = 0; i < arr.length; i++) {
if ((arr[i] & mask) == 0) {
firstOdd ^= arr[i];
}
}
int secondOdd = firstOdd ^ odds;
System.out.println(firstOdd);
System.out.println(secondOdd);
}
private static int oneAtTheMostRightSide(int a) {
int aa = ~a + 1;
int aaa = a & (aa);
return aaa;
}
}
Below is the output of above code snippet :
5
3
4.8 Check a number is power of 2
public class BitOperationsTest16 {
public static void main(String[] args) {
System.out.println(isPowerOf2(1));
System.out.println(isPowerOf2(2));
System.out.println(isPowerOf2(3));
System.out.println(isPowerOf2(4));
System.out.println(isPowerOf2(5));
System.out.println(isPowerOf2(6));
System.out.println(isPowerOf2(7));
System.out.println(isPowerOf2(8));
System.out.println(isPowerOf2(9));
}
private static boolean isPowerOf2(int a) {
if(a < 0) {
return false;
}
return a == oneAtTheMostRightSide(a);
}
private static int oneAtTheMostRightSide(int a) {
int aa = a & -a;
return aa;
}
}
The output of above code snippet is below :
true
true
false
true
false
false
false
true
false
4.9 Arithmetic operations using bit operations
Without using any arithmetic operations (+ – * /), it is possible to achieve the same by using bit operations.
public class BitOperationsTest18 {
public static void main(String[] args) {
int a = -5;
int b = 3;
int d = add(a, b);
System.out.println(a + " + " + b + " = " + d);
int e = sub(a, b);
System.out.println(a + " - " + b + " = " + e);
int f = mul(a, b);
System.out.println(a + " * " + b + " = " + f);
int g = div(a, b);
System.out.println(a + " / " + b + " = " + g);
}
private static int div(int a, int b) {
if (b == 0) {
throw new ArithmeticException("div by 0");
}
int aa = abs(a);
int bb = abs(b);
if (aa < bb) {
return 0;
}
int c = 0;
while (aa >= bb) {
aa = sub(aa, bb);
c = add(c, 1);
}
if (pos(a) && !pos(b) || !pos(a) && pos(b)) {
c = neg(c);
}
return c;
}
private static int abs(int a) {
if (!pos(a)) {
return neg(a);
}
return a;
}
private static int mul(int a, int b) {
int c = 0;
if (pos(a) && !pos(b)) {
for (int i = 0; i < neg(b); i++) {
c = add(c, a);
}
c = neg(c);
} else if (!pos(a) && pos(b)) {
for (int i = 0; i < neg(a); i++) {
c = add(c, b);
}
c = neg(c);
} else if (!pos(a) && !pos(b)) {
for (int i = 0; i < neg(a); i++) {
c = add(c, neg(b));
}
} else {
for (int i = 0; i < a; i++) {
c = add(c, b);
}
}
return c;
}
private static boolean pos(int a) {
int mask = 1 << 31;
return (a & mask) == 0;
}
private static int add(int a, int b) {
int aa = a ^ b;
int bb = (a & b) << 1;
if (bb == 0) {
return aa;
}
return add(aa, bb);
}
private static int sub(int a, int b) {
return add(a, neg(b));
}
private static int neg(int a) {
return add(~a, 1);
}
}
The output of above code snippet is below :
-5 + 3 = -2
-5 - 3 = -8
-5 * 3 = -15
-5 / 3 = -1
4.10 Multiply or Divide a positive number by 2^n using bit shift operators
For a non-negative number :
- Left shifting by one is equivalent to multiplying it by 2, or, in general, left shifting by n positions is equivalent to multiplication by 2^n;
- Right shifting by one is equivalent to dividing it by 2, or, in general, right shifting by n positions is equivalent to division by 2^n.
public class BitOperationsTest19 {
public static void main(String[] args) {
int a = 4;
System.out.println(a);
System.out.println();
System.out.println(a << 1);
System.out.println(a << 2);
System.out.println();
System.out.println(a >> 1);
System.out.println(a >> 2);
}
}
The output of above code snippet is below :
4
8
16
2
1
4.11 BitSet
For a positive number n, if we want to check any number from 0 to n is present or not, we may use boolean array as the data structure.
However, each boolean member in a boolean array usually consumes one byte instead of just one bit.
So when we have tight memory requirements, or we are just aiming for a reduced memory footprint, boolean array is far from being ideal.
That is where the BitSet comes in, it is a combination of numeric data types (such as int) and bit-wise operations.
public class BitOperationsTest17 {
public static void main(String[] args) {
BitSet set = new BitSet(36);
set.show();
int num = 33;
System.out.println("add " + num);
set.add(num);
System.out.println("contains " + num + " : " + set.contains(num));
set.show();
System.out.println("remove " + num);
set.remove(num);
System.out.println("contains " + num + " : " + set.contains(num));
set.show();
}
private static class BitSet {
private int[] set;
private int max;
BitSet(int max) {
this.max = max;
int size = this.max / 32 + 1;
set = new int[size];
}
void add(int num) {
if (num > this.max) {
return;
}
int m = num / 32;
int n = num % 32;
this.set[m] |= (1 << n);
}
void remove(int num) {
if (num > this.max) {
return;
}
int m = num / 32;
int n = num % 32;
this.set[m] &= ~(1 << n);
}
boolean contains(int num) {
if (num > this.max) {
return false;
}
int m = num / 32;
int n = num % 32;
return (this.set[m] & (1 << n)) != 0;
}
void show() {
String bits = "";
for (int i = 0; i < this.set.length; i++) {
bits += binary(this.set[i], false);
bits += '|';
}
System.out.println(bits);
}
String binary(int num, boolean withoutLeadingZero) {
String bits = "";
for (int i = 0; i < 32; i++) {
int mask = (1 << i);
if ((num & mask) == 0) {
if (!withoutLeadingZero) {
bits += '0';
} else {
if (bits != "") {
bits += '0';
}
}
} else {
bits += '1';
}
}
return bits;
}
}
}
Below is the output of above code snippet :
00000000000000000000000000000000|00000000000000000000000000000000|
add 33
contains 33 : true
00000000000000000000000000000000|01000000000000000000000000000000|
remove 33
contains 33 : false
00000000000000000000000000000000|00000000000000000000000000000000|
4.12 Set or unset the given bit position of an integer
public class BitOperationsTest20 {
public static void main(String[] args) {
int a = 11;
System.out.println(a);
for (int i = 31; i >= 0; i--) {
if (isSet(a, i)) {
System.out.print("1");
} else {
System.out.print("0");
}
}
System.out.println();
int b = setBit(a, 2);
System.out.println(b);
int c = unsetBit(b, 2);
System.out.println(c);
}
// to check if the given bit position in x is set (1).
private static boolean isSet(int x, int pos) {
int bit = x & (1 << pos);
if (bit == 0) {
return false;
}
return true;
}
// to set the given bit position in x to 1.
private static int setBit(int x, int pos) {
return x |= (1 << pos);
}
// to unset the given bit position in x (set it to 0).
private static int unsetBit(int x, int pos) {
return x &= ~(1 << pos);
}
}
The output of above code snippet is below :
11
00000000000000000000000000001011
15
11