Bit Manipulation Problems (4)

Let's look at another medium level problem and solve it with bitwise manipulation

Q397 Integer Replacement



Without bit operation, you might think of a solution with time complexity of O(logN),
 since we need a loop for n/2 until n becomes 1

 Let's first look at the mid-results in binary number when n = 8

 num:    8        binary:    00001000
 num:    4        binary:    00000100
 num:    2        binary:    00000010
 num:    1        binary:    00000001

 if the original number takes 4 bits then it will take 4 steps
 so the problem become a shift-operation problem
 we just need >> right-shift to count the bits shifted until the number becomes 0
 and we will be able to write a O(1) solution
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/BitManipulation/Q397IntegerReplacement.playground/Contents.swift



Other bit manipulation problems in my blog:
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-1.html
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-2.html
http://hadesmercury.blogspot.com/2019/03/bit-manipulation-problems-3.html

More bit manipulation problems at Leetcode:
https://leetcode.com/tag/bit-manipulation/