https://hadesmercury.blogspot.com/2019/03/bitwise-operator-basics.html
More Bit Manipulation Problems:
https://leetcode.com/tag/bit-manipulation/
Q342 Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
Sample solution:
https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/BitManipulation/Q342PowerOfFour.playground/Contents.swift
num: 4 binary: 00000100
num: 16 binary: 00010000
num: 64 binary: 01000000
Similar approach to solve Power of Two. But the difference is the how many bits we care.
Solving Power of Four we care about 3 bits, if the last 3 bits is '100', so instead of & 1 to check the last 3 bits, we use '& 7' (& 111) and we count the number of '100' we have found
if it is '100' we increase the count, return false if the count > 1
if it is '000' we can shift right by 2
if it is other value besides of '100' or '000', then it can not be a power of 4, return false directly
We will be able to find another solution by introducing 0x55555555,
0x55555555 = 0101 0101 ... 0101
0xaaaaaaaa = 1010 1010 ... 1010
For a power of 4: n, n & 0x55555555 should be n
Other solutions, I am not going to cover so much in this page
The last solution based on the formula, however the solution doesn't work in Swift neither in Java. Try C++.
No comments:
Post a Comment