Session 5: Math1 & Math2

Original Session

Date: 9 Nov 2024

1. Topic: Math 1
   1. Concept Bit Manipulation.
      1. operator
         1. and = &
         2. or = |
         3. xor = ^
         4. complement = ~
      2. Concept: Power of 2
         1. if Number is power of 2 then n & (n-1) == 0
            1. 8 & 7 = 0 using bitwise &.
      3. Concept: Remove one bit from right.
         1. Formula : n & n-1
         2. Find first bit from right.
         3. complement (~) all bits from this bit to the right, rest of the bits of left will be the same.
         4. Make & operation with original bits and newly created bit after complement operation.
         5. This will remove one bit from right.
         6. To remove all bits keep doing this operation in loop until 0;
         7. n = n & n-1 until 0 will remove one bit each time.
         8. If n is even, n-1 will be last bit to zero.
         9. If n is odd, n-1 will be complement all bits to right starting from right most set bit
            1. n = 9
               bit = 1 0 0 1
               n-1 = 8
               bit = 1 0 0 0
               
            2. n = 6
               bit = 1 1 0
               n-1 = 5
               bit = 1 0 1
               
      4. Concept: Last Set Bit
         1. Formula : n & ~(n-1)
            1. n = 8 bit 1 0 0 0
               n - 1 = 7 bit 0 1 1 1
               ~(n-1) = ~(7) bit 1 0 0 0
               n & ~(n-1) = 1 0 0 0 & 1 0 0 0
               
               
            2. n = 11 bit 1 0 1 1
               n-1 = 10 bit 1 0 1 0
               ~(n-1) = 0 1 0 1
               n & ~(n-1) = 0 0 0 1
               
      5. Concept: All Odd positioned bits
         1. 0xAAAAAAAA

      
      
      
      

2. Convert Integer to Binary
   1. Code

   void toBinary(int N) {
   		//Write your code here
   		
   		
   		List<Integer> list = new ArrayList();
   		while (N >= 1) {
   		    
   		    list.add(N%2);
   		    N = N/2;
   		}
   		
   		Collections.reverse(list);
   		
   		for (int value: list) {
   		 System.out.print(String.valueOf(value));   
   		}
   	}

3. Leetcode 136. Single Number
   1. code

   public int singleNumber(int[] nums) {
           
           int num = 0;
   
           for (int value: nums) {
               num ^= value;
           }
   
           return num;
       }

4. leetcode 231. Power of Two
   1. code

   public boolean isPowerOfTwo(int N) {
           
           if (N<=0) {
               return false;
           }
   
           if ( (N & (N-1)) == 0) {
               return true;
           }
   
           return false;
       }

5. leetcode 191. Number of 1 Bits
   1. code

   public int hammingWeight(int n) {
           
           int count = 0;
           while (n>0) {
   
               n = n&n-1;
               count ++;
           }
   
           return count;
       }

6. 389. Find the Difference
   1. Bits with Stream

      public char findTheDifference(String s, String t) {
           
              char sXor = (char)s.chars().reduce(0, (a,b) -> a^b);
              char tXor = (char)t.chars().reduce(0, (a,b) -> a^b);
              return (char)(sXor^tXor);
          }

   2. Bits with two pointers

       public char findTheDifference(String s, String t) {
              
              int left = 0;
              char ch = (char)0;
      
              while (left < t.length()) {
      
                  if (left < s.length()) {
                      ch^=s.charAt(left);
                  }
      
                  if (left < t.length()) {
                      ch^=t.charAt(left);
                  }
                  left ++;
              }
              return ch;
          }

7. leetcode 342. Power of Four
   1. code
      1. Bitmanipulation

         public boolean isPowerOfFour(int n) {
                 
                 return (n > 0) && ((n&(n-1)) == 0) && ((n&0xAAAAAAAA) == 0);
             }

      2. Math

         public boolean isPowerOfFour(int n) {
                 
                 if (n<=0) {
                     return false;
                 }
         
                 while (n > 1) {
         
                     if (n%4 > 0) {
                         return false;
                     }
                     n = n/4;
                 }
         
                 return true;
             }

8. leetcode 260. Single Number III
   1. leetcode here

   public int[] singleNumber(int[] nums) {
           
           int x = 0; 
           int y = 0;
           int xor = 0;
   
           // Find remained bits
           for (int i = 0; i < nums.length; i++) {
               xor ^= nums[i];
           }
   
           // Find last set bit from ramained bits
           int lastSetBit = xor & ~(xor - 1);
   
           // seggregate the bucket which have and havenot lastSet bit.
           for (int i = 0; i < nums.length; i++) {
               
               if ((lastSetBit & nums[i]) == 0) {
                   // havenot
                   x ^= nums[i];
               } else {
                   // have
                   y ^= nums[i];
               }
           }
   
           return new int[] {x, y};
       }

9. leetcode 137. Single Number II
   1. leetcode here

   public int singleNumber(int[] nums) {
           
           int n = nums.length;
           int ans = 0;
           int bitPositionToPower = 0;
           
           for (int index = 0; index < 32; index ++) {
   
                   int countBit = 0;
   
                   for (int j = 0; j < n; j ++) {                    
                       countBit += nums[j] & 1;
                       nums[j] = nums[j] >> 1;
                   }
   
                   if (((countBit % 3) & 1) == 1) {
   		                // does not have bit 3 times
                       ans += Math.pow(2, bitPositionToPower);
                   }
   
                   bitPositionToPower ++;
           }
   
           return ans;
       }