【LeetCode】190 & 191

190 - Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

Solution 1:

 1  class Solution {
 2  public:
 3     uint32_t reverseBits(uint32_t n) {      //runtime:4ms
 4         unsigned ret = 0;
 5         unsigned x = 1 << 31;
 6         unsigned y = 1;
 7         while(x){
 8             if(x & n)ret |= y;   //或ret += y;
 9             x >>= 1;
10             y <<= 1;
11          }
12          return ret;
13      }
14  };

Solution 2:

 1  class Solution {
 2  public:
 3     uint32_t reverseBits(uint32_t n) {      //runtime:4ms
 4         unsigned int bit = 0;
 5         unsigned int result = 0;
 6         while(bit<32)
 7         {
 8             if((n>>bit) & 1 == 1)
 9                 result = result + (1<<(31-bit));
10             bit ++;
11         }
12     
13         return result;
14     }
15  };

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.

Solution：n&(n-1)实现n与n-1的按位与，消除最后一位1

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