Code 1 : Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

Example 1

Input: n = 1
Output: true
Explanation: 2^0 = 1

Example 2

Input: n = 16
Output: true
Explanation: 2^4 = 16

Example 3

Input: n = 3
Output: false

Example 4

Input: n = 4
Output: true

Example 5

Input: n = 5
Output: false

Solution

常规思路

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n==0) return false;
		while(n%2==0){
			n/=2;
		}
		if(n!=1) return false;
		else return true;
    }
};

其实还是使用了循环，这道题的本意是用位运算做。

位运算

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n<=0) return false;
		if (n&(n-1)) return false;
		else return true;
    }
};

• 常用位操作

判断奇偶

(x & 1) == 1 —等价—> (x % 2 == 1)
(x & 1) == 0 —等价—> (x % 2 == 0)
x / 2 —等价—> x >> 1
x &= (x - 1) ------> 把x最低位的二进制1给去掉
x & -x -----> 得到最低位的1
x & ~x -----> 0

指定位置的位运算

将X最右边的n位清零：x & (~0 << n)
获取x的第n位值：(x >> n) & 1
获取x的第n位的幂值：x & (1 << n)
仅将第n位置为1：x | (1 << n)
仅将第n位置为0：x & (~(1 << n))
将x最高位至第n位（含）清零：x & ((1 << n) - 1)
将第n位至第0位（含）清零：x & (~((1 << (n + 1)) - 1))

异或结合律

x ^ 0 = x, x ^ x = 0
x ^ (~0) = ~x, x ^ (~x) = ~0
a ^ b = c, a ^ c = b, b ^ c = a

这道题x & (x - 1) 相当于把x的最低位1去掉了来判断是否全为0（二进制中二的倍数只有一个1）

Code 2 ：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).

Example 1

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Solution

去掉最后的0

class Solution {
public:
    int hammingWeight(uint32_t n) {
    	int count=0;
    	while(n){ 
			n&=(n-1);
			count++;
		}  
		return count;
    }
};

上道题带来的灵感，不断地去掉最后一个0，记录去掉了几次，直到n全为0为止。

循环检测每一位是否为1

class Solution {
public:
    int hammingWeight(uint32_t n) {
    	int count=0;
    	while(n){ 
    		count+=(n&1);
    		n>>=1;
		}
		return count;
    }
};

注意右移符号>>= , 取最后一位n&1 。

Code 3 : Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

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

Example 1

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Solution

遍历

using namespace std;
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
    	uint32_t ans=0;
        for(int i=31;i>=0;i--){
        	ans+=((n>>i)&1)*pow(2,31-i);
		}
		return ans;
    }
};

从最后向前遍历的常规思路（注意(n>>i)&1表示取n的第i个）

移动

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
    	uint32_t ans=0;
    	for(int i=0;i<32;i++){
    		ans=(ans<<1)|(n&1);
    		n>>=1;
		}
		return ans;
    }
};

每次把ans向左移动一个，取n的最后一个加到ans后面（此时ans最后一位是0，取并集可以直接相加）,然后再把n向右移动一个。

分治法（没有那么理解）

class Solution {
private:
    const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
    const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
    const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111

public:
    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};

分而治之，先两个两个交换，然后四个四个交换…最后十六个十六个交换。

Code 4 : Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1

Input: nums = [2,2,1]
Output: 1

Example 2

Input: nums = [4,1,2,1,2]
Output: 4

Example 3

Input: nums = [1]
Output: 1

Solution

使用map

class Solution {
public:
   int singleNumber(vector<int>& nums) {
   	int n=nums.size();
   	int ans;
   	map<int,bool> a;
   	for(int i=0;i<n;i++){
   		if(a.find(nums[i])!=a.end()){
                a[nums[i]]=false;
           }
   		else{
                a[nums[i]]=true;
           }
   	}
   	for(auto it=a.begin();it!=a.end();it++) {
           if (it->second) ans=it->first;
       }
   	return ans;
   
   }
};

注意map的使用方法

• 判断是否存在a.find(nums[i])!=a.end()(如果不存在返回的是end)
• 可直接插入（没必要用insert()）
• 迭代器遍历for(auto it=a.begin();it!=a.end();it++)，找key用first()，找value用second()

异或算法

class Solution {
public:
    int singleNumber(vector<int>& nums) {
    	int ans=nums[0];
		for(int i=1;i<nums.size();i++){
			ans^=nums[i];
		}
		return ans;
	}
};

异或运算中相同的都是0，这个算法最后会把相同的都变成0,然后0和任何数的异或都是任何数。