首页 > 代码库 > LeetCode191 Number of 1 Bits. LeetCode231 Power of Two. LeetCode342 Power of Four

LeetCode191 Number of 1 Bits. LeetCode231 Power of Two. LeetCode342 Power of Four

位运算相关 三道题

231. Power of Two

Given an integer, write a function to determine if it is a power of two. (Easy)

分析:

数字相关题有的可以考虑用位运算,例如&可以作为筛选器。

比如n & (n - 1) 可以将n的最低位1删除,所以判断n是否为2的幂,即判断(n & (n - 1) == 0)

 

代码:

1 class Solution {
2 public:
3     bool isPowerOfTwo(int n) {
4         if (n <= 0) {
5             return false;
6         }
7         return ( (n & (n - 1)) == 0);  //按位筛选,考虑位操作
8     }
9 };

191. 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. (Easy)

 

分析:

同上一个题,n & n-1可以去掉n的最低位1,因此循环即可求出1的个数。

代码:

 1 class Solution {
 2 public:
 3     int hammingWeight(uint32_t n) {
 4         int num = 0;
 5         while (n > 0) {
 6             n = (n & (n - 1));
 7             num++;
 8         }
 9         return num;
10     }
11 };

 

342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4. (Easy)

分析:

首先是4的幂肯定是2的幂,所以可以利用Power of Two, 其次考察 4, 16等数,其1出现在奇数位。

所以利用0101 &该数,可以删选掉是2的幂但不是4的幂。

代码:

1 class Solution {
2 public:
3     bool isPowerOfFour(int num) {
4         if (num <= 0) {
5             return false;
6         }
7         return ( (num & (num - 1)) == 0 && (num & 0x55555555) ); //有一个1,且1在奇数位上,&操作起到筛选器作用,5即0101
8     }
9 };

 

LeetCode191 Number of 1 Bits. LeetCode231 Power of Two. LeetCode342 Power of Four