Bit Manipulation Problems (1)

Bitwise Operation Basics:
https://hadesmercury.blogspot.com/2019/03/bitwise-operator-basics.html


Now we are going to solve problems with the help of  bit operators

Leetcode  Q231  Power of Two
Given an integer, write a function to determine if it is a power of two.
Sample solution:
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/BitManipulation/Q231PowerOfTwo.playground/Contents.swift

A normal approach will be using while loop to divide by 2 and end up with time complexity of O(log n)


If use bit operations, we can achieve time complexity of O(1)
As a power of 2, its binary presentation always contains only-one 1
Coming up with an approach: count the number of 1s
We need >> to shift the bits and '& 1' (& 00000001) to check if the last bit is 1


Another approach:
First, observer binary of n and n - 1

 num:    16        binary:    00010000
 num:    15        binary:    00001111
 num:    32        binary:    00100000
 num:    31        binary:    00011111

If the result of n & (n - 1) should always be 0, if n is a power of 2






We've already solved the problem below, which is similar to the core calculation of isPowerOfTwo1(num: Int)

Q191 Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.




More Bit Manipulation Problems: 
https://leetcode.com/tag/bit-manipulation/

More Solutions - check my other tutorial:
https://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-2.html