Bitwise Operations (Primitive Types)

A bitwise operation is an operation that operates on bits and performs bit-by-bit manipulation.
The most Commonly used bitwise operations are:

1. AND  : (a & b) 
2. OR   : (a | b) : 
3. XOR  : (a ^ b) : Exclusive OR
4. NOT  : (~a) : Inverts all the bits
5. Left Shift : (a << b) :Matheamatically equivalent to a * 2^b
6. Right Shift:
    1. Arithmetic Right Shift : (a >> b) :Mathematically, a >> b is equivalent to a / 2^b
    2. Logical Right Shift : (a >>> b)  :Mathematically, a >>> b is equivalent to a / 2^b treating a as unsigned

A combination of these basic bitwise operations can be used to perform complex operations.
Some complex of bitwise operations developed from the basics mentioned above include:

1. Set a bit at a given position : (a | (1 << b))
2. Clear a bit at a given position : (a & ~(1 << b))
3. Toggle a bit at a given position : (a ^ (1 << b))
4. Check if a bit is set at a given position : ((a & (1 << b)) != 0)
5. Check if a bit is clear at a given position : ((a & (1 << b)) == 0)
6. Clear all bits from the most significant bit through i (inclusive) : (a & ((1 << i) - 1))
7. Clear all bits from i through 0 (inclusive) : (a & (~((1 << (i + 1)) - 1)))
8. Update a bit at a given position : (a & ~(1 << b)) | (value << b)
9. Clear the least significant bit : (a & (a - 1))
10. Isolate the least significant bit : (a & ~(a - 1))
11. Isolate the rightmost set bit : (a & (-a))
12. Isolate the rightmost 0 bit : (a | (a + 1))
13. Isolate the rightmost 1 bit : (a | (a - 1))

AND Bitwise Operation

The bitwise AND of a and b is a new integer c such that the value of c is 1 at a bit position if and only if the corresponding bits of a and b are both 1. In other words, c has a 1 bit at each bit position for which the corresponding bits of a and b both have a 1 bit.

//a= 5(00000101), b = 3(00000011)
//a & b = 1(00000001) Decimal value of 1 is 1
public static int and(int a, int b) {
    return a & b;
}

XOR Bitwise Operation

The bitwise XOR of a and b is a new integer c such that the value of c is 1 at a bit position if and only if the corresponding bits of a and b are different. In other words, c has a 1 bit at each bit position for which the corresponding bits of a and b are different.

//a= 5(00000101), b = 3(00000011)
//a ^ b = 6(00000110) Decimal value of 6 is 6
public static int xor(int a, int b) {
    return a ^ b;
}

1st Complement Bitwise Operation

The bitwise complement of a is a new integer c such that the value of c is 1 at a bit position if and only if the corresponding bit of a is 0. In other words, c has a 1 bit at each bit position for which the corresponding bit of a is 0.

//a= 5(00000101)
//~a = -6(11111010) Decimal value of -6 is -6
public static int complement(int a) {
    return ~a;
}

2nd Complement Bitwise Operation

After the 1st complement, the 2nd complement is obtained by adding 1 to the 1st complement.

//a= 5(00000101)
//~a = -6(11111010) Decimal value of -6 is -6
//~a + 1 = -5(11111011) Decimal value of -5 is -5
public static int complement(int a) {
    return ~a + 1;
}

Using 2's complement to represent negative numbers

The 2's complement of a number is the number obtained by inverting all the bits of the number and adding 1 to the result. For example, the 2's complement of 5 is -6. The 2's complement of a number is the negative of the number. The 2's complement of a number is also called the 1's complement of the number's negative.

Shift Bitwise Operation

Left Shift Bitwise Operation

Let a be an integer. The bitwise left shift of a by b is a new integer c such that the value of c is a * 2^b. In other words, c has a 1 bit at each bit position for which the corresponding bit of a is 1.

//a= 5(00000101)
//a << 1 = 10(00001010) Decimal value of 10 is 10 :Mathematically, a << b is equivalent to a * 2^b
public static int leftShift(int a) {
    return a << 1;
}

Common Bitwise Operations LeeetCode Problem(222. Count Complete Tree Nodes)

Tip: Complete binary Tree.(It can have between 1 and 2^h nodes inclusive at the last level h)

public class a222CountCompleteTreeNodes {
      public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int left = countLevel(root.left);
        int right = countLevel(root.right);

        if (left == right) { 
            //Both left and right has same numbers of nodes
            ////(1 << left); : 2^left
            return countNodes(root.right) + (1 << left);
        } else {
            // left and right has different numbers of nodes
            //(1 << right); : 2^right
            return countNodes(root.left) + (1 << right);
        } 
    }

    //checking the levels of the tree
    private int countLevel(TreeNode n) {
        int level = 0;
        while (node != null) {
            level++;
            node = node.left;
        }
        return level;
    }

}

Right Shift Bitwise Operation

Let a be an integer. The bitwise right shift of a by b is a new integer c such that the value of c is a / 2^b. In other words, c has a 1 bit at each bit position for which the corresponding bit of a is 1.

//a= 5(00000101)
//a >> 1 = 2(00000010) Decimal value of 2 is 2 :Mathematically, a >> b is equivalent to a / 2^b
public static int rightShift(int a) {
    return a >> 1;
}

Unsigned Right Shift Bitwise Operation

Denoted by >>>. It is the same as >> except that it always fills 0 regardless of the sign of a.

//a= 5(00000101)
//a >>> 1 = 2(00000010) Decimal value of 2 is 2 :Mathematically, a >>> b is equivalent to a / 2^b
public static int unsignedRightShift(int a) {
    return a >>> 1;
}

References

tutorialspoint
javatpoint
baeldung
programiz
Medium
geeksforgeeks
geeksforgeeks