位运算

2017-04-11 | 阅读：次

二进制编码：原码、反码以及补码

原码：第一位符号位加真值。如：0000 0001 是1的原码， 1000 0001 是-1的原码
反码：正数的反码是其本身,负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.
补码：正数的补码就是其本身，负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

为何会出现三种编码形式？
简化运算，让符号位也参与运算。比如减法也可用加上一个负数运算，在这种情况下，原码和补码的编码运算会出现错误：
1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2
1 - 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原= [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0 (符号无意义)
而用补码表示时的运算：
1-1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原 = [0000 0001]补 + [1111 1111]补 = [0000 0000]补=[0000 0000]原
并且，补码可以表示到-128 (8位时，即 -（2^(n-1))): (-1) + (-127) = [1000 0001]原 + [1111 1111]原 = [1111 1111]补 + [1000 0001]补 = [1000 0000]补

再略深入的原理参见博客
https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html

位运算符

& 与
或
^ 异或
~ 取反：对整数的每一位取反，符号也位取反「取反：0取反为1，1取反为0， ~9 = -10
« 左移: 把 x 的二进制位向左移动 n 个单位，高位丢弃，低位补0
[ » ] 右移:把 x 的二进制位向右移动 n 个单位，低位丢弃，符号位不变

位运算应用小技巧

计算某个整数二进制表示中1的个数：i&(i-1)可以减少原数字中1个1，知道原数字i变为0，记录变换次数。对于负数，要特殊处理一下，先将负数&0X7FFFFFFFF,再按正数计算，最后加1
```
  int cntOne = 0;
  while(i > 0){
    i = i & (i - 1);
    cntOne++;
  }
```
奇偶判断： i&1?printf(“奇数\n”):printf(“偶数\n”);
每位^1可以对此位取反
a ^ b = c 则 a = b ^ c

leetcode例题解析

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 231.

思路：异或后算1的个数

int hammingDistance(int x, int y) {
       int z = x ^ y;
     int count = 0;
     while(z){
       count++;
       z = z & (z-1);
     }
     return count;
   }

477. Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

思路：两两算起来相加可以，但是有更快的方法，所有数的每一位，算出几个1，假设n个，那这个位的距离就是（size - n） *ｎ

int totalHammingDistance(vector<int>& nums) {
       int re = 0;
       while(true){
           int doneNum = 0;
           int num1 = 0;
           for(int i = 0; i < nums.size(); i++){
              int tmp = nums[i] & 1;
               nums[i] = nums[i] >> 1;
               if(nums[i] == 0){
                       doneNum++;
               }
                   if(tmp){
                       num1++;
                   }
           }
           re += num1 * (nums.size() - num1);
           if(doneNum == nums.size()){
               break;
           }
       }
       return re;
   }

476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note: The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation.

思路：~num 可以各个位取反，但是也会把前面的0取反了，比如5的二进制表示：0000 0000 0000 0000 0000 0000 0000 0101 ，会把前边的0也变1，所以需要把前面的0 给遮掩掉。

  int findComplement(int num) {
        int mask = ~0;
        while(num & mask){
            mask <<= 1;
        }
        return ~mask & ~num;
    }

421. Maximum XOR of Two Numbers in an Array

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

Example:

Input: [3, 10, 5, 25, 2, 8]

Output: 28

Explanation: The maximum result is 5 ^ 25 = 28.

思路：要求o(n), 考虑对n个数的每一位操作。从高位开始，判断此位能不能异或出1来。

（1）可以用hash表，把从高位开始到当前遍历的位所表示的数字存起来，看看能不能用其中两个异或出当前位为1的结果，用的小技巧： a ^ b = c 则 a = b ^ c

int findMaximumXOR(vector<int>& nums) {
      int mask = 1;
      int max = 0;
      for(int i = 31; i >=0; i--){
          mask = mask | (1 << i);
          unordered_set<int> set;
          for(int j = 0; j < nums.size(); j++){
              int tmp = (nums[j] & mask) >> i;
              if(!set.count(tmp)){
                  set.insert(tmp);
              }
          }
          int attempMax = (max << 1) | 1;
          unordered_set<int>::iterator it;
          for(it  = set.begin(); it!= set.end();it++){
              int nn = *it;
              if(set.count(nn ^ attempMax)){
                  break;
              }
          }
          if(it!=set.end()){
              max = attempMax;
          }else{
              max = max << 1;
          }
      }
      return max;
  }

（2）可以用树，构建出31-0位的所有0,1选择，然后对每个数，求出异或，返回最大的那个

class Solution {
public:
 class TreeNode {
  public:
      TreeNode* next[2];
      TreeNode () {next[0] = NULL; next[1] = NULL;};
  };
  TreeNode* buildTree(vector<int>& nums) {
      TreeNode* root = new TreeNode(), *cur;
      int n = nums.size();
      for (int i = 0; i < n; i++) {
          int num = nums[i];
          cur = root;
          for (int j = 31; j >= 0; j--) {
              int index = ((num >> j) & 1);
              if (cur->next[index] ==  NULL)
                  cur->next[index] = new TreeNode();
              cur = cur->next[index];
          }
      }
      return root;
  }

  int helper(TreeNode* cur, int num) {
      int res = 0;
      for (int i = 31; i >= 0; i--) {
          int index = ((num >> i) & 1) ? 0 : 1;
          if (cur->next[index]) {
              res = (res<<1) + 1;
              cur = cur->next[index];
          } else {
              res = res<<1;
              cur = cur->next[index ? 0 : 1];
          }
      }
      return res;
  }

  int findMaximumXOR(vector<int>& nums) {
      int res = 0;
      TreeNode* root = buildTree(nums);

      for (auto i : nums) {
          res = max(res, helper(root, i));
      }

      return res;
  }
};

405. Convert a Number to Hexadecimal

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character. The given number is guaranteed to fit within the range of a 32-bit signed integer. You must not use any method provided by the library which converts/formats the number to hex directly.

思路:每四位求一个数，然后拼接起来，从后往前，&F(15),然后原数字右移4位，循环8次，中间如果变为0了跳出循环

  string toHex(int num) {
    	string str = "";
    	if(num == 0){
    	    return "0";
    	}
    	int mask = 15;//~((~0) << 4);
    	for (int i = 0; i < 8; i++) {
    		int s = mask & (num);
    		if (s < 10) {
    			str = (char)((char) s + '0') + str;
    		} else {
    			str = (char)((char) (s - 10) + 'a') + str;
    		}
    		num >>= 4;
    		if(num == 0){
    			break;
    		}
    	}
	    return str;
    }