LeetCode :【Easy】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.

- My train of thought:

一开始就想用位运算搞定吧，但是发现好像不行hh，顺便复习了一下负数补码的概念 note：负数在C语言中以补码形式存储，计算原码真值时，应减一再取反（不包括符号位） 比如说 int型整数 5，取反~5之后，得到的值是-6 0000，101->1111，010，这样虽然数值位取反了，但是输出结果并不对。 没有往复杂了想，盯了一会儿草稿纸，发现其实101+010=111，so，111-101=010，达成目标！

- My solution:

int findComplement(int num) { int org,comp,dist=0,a; org=num; while(num>1) { dist++; num=num/2; } dist++; a=(int)pow(2,dist)-1; comp=a-org; return comp; }

run time： 3ms

- Better Solution

class Solution { public: int findComplement(int num) { unsigned mask = ~0; while (num & mask) mask <<= 1; return ~mask & ~num; } };

关于unsigned

整型的每一种都分有无符号（unsigned）和有符号（signed）两种类型（float和double总是带符号的），unsigned n，则n的最高位不表示符号

unsigned mask = ~0;/*mask=11111 111*/ while (num & mask) /*num的位数*/ mask <<= 1;/*mask=11111 000*/

关于<< >>

左移运算符“<<”把“运算数的各二进位全部左移若干位由“<<”右边的数指定移动的位数，高位丢弃，低位补0。 对于有符号数，在右移时，符号位将随同移动。当为正数时， 最高位补0，而为负数时，符号位为1，最高位是补0或是补1 取决于编译系统的规定。

这里发现其实在使用<<时，是没有必要使用unsigned的，但是这是个好习惯，可以不用特意再去区分左移还是右移。

~mask & ~num;/*00000 111 & 11111 010*/

到这一步才真的明白意图，按照我原本的思路，5取反之后是-6，因为有符号位，想到这我就放弃了，但其实应该进一步往下想，要保留数值位，把符号位取反的策略，就是要构造一个符号位全为0，数值位全为1的二进制数。 while循环的作用是算出数值位的位数，又可以直接得到构造的数，非常巧妙了。