每日编程中遇到任何疑问、意见、建议请公众号留言或直接撩Q474356284(备注每日编程)

今日问题：

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

注意:

1. 给定的整数保证在32位带符号整数的范围内。

2. 你可以假定二进制数不包含前导零位。

示例 1:

输入: 5

输出: 2

解释: 5的二进制表示为101(没有前导零位)，其补数为010。所以你需要输出2。

示例 2:

输入: 1

输出: 0

解释: 1的二进制表示为1(没有前导零位)，其补数为0。所以你需要输出0。

---

解决方法：

首先说一下：

这里的补数“不是“之前你学过的补码哦。

虽然在计算机科学中补码的概念是来源于数学中的补数的。

需要注意的一点是本题求正整数的原码的时候需要忽略前导零位。

什么意思呢？

举个栗子：比如5，二进制是101，那么它的补数就是010，十进制就是2.

但是！但是！但是！计算机不是这样想的！

按照int来计算的话，int是多少位的？(下面这段话选看)

(在不同编译器中，可能不一样，比如在32位和64位编译器下，int都是4个字节，也就是32位。(你也许又会问32位和64位为什么都是4个字节，回答是：这是规定啊！需要说明一下的是指针类型存储的是所指向变量的地址，所以32位机器只需要32bit，而64位机器需要64bit。)

那么，int占用4个字节，32位。

5的二进制就是1000,0000,0000,0000,0000,0000,0000,0101.

则它的反码就是0111, 1111, 1111,1111, 1111, 1111, 1111,1010.

显然，将其直接取反，再输出为十进制就不符合题意了。

算法思想(一)：

① 寻找一个掩码(mask)

要找的这个掩码的特征应该是这个样子的。5的二进制是101，只占3个bit，那么这个掩码的最后3个bit要是0，其余全部是1。如下所示：

5：0000 0101

掩码：1111 1000

② 分别取反

~5 ：1111 1010

~掩码：0000 0111

③ 相与

~5 & ~掩码 = 0000 0010

算法思想二：

return      pow(2,int(log2(num))+1) - 1 -num;

//图片代码中以注释的方式写出。

Java算法思想(三)：

return      ~num & (Integer.highestOneBit(num) - 1);

以上各个符号的作用:

①Integer.highestOneBit(num)：取num的二进制数最左边的最高位，且高位后面全部补零，最后返回int型的结果。

②-1：因为经过上面的步骤，只有最高位为1其余位都为0这样再减一就会导致借位直到借到最高位，结果得到 最高位为0其余位都为1相当于取反了

③&：对两个二进制数进行按位与运算，例101& 010得000；

101&111得101。                                        

④~ ：对一个数的二进制取反

C++代码：

C代码：

Java代码：

---

明日题目预告：

唯一摩尔斯密码词

国际摩尔斯密码定义一种标准编码方式，将每个字母对应于一个由一系列点和短线组成的字符串， 比如: "a" 对应 ".-", "b" 对应 "-...", "c" 对应 "-.-.", 等等。

为了方便，所有26个英文字母对应摩尔斯密码表如下：

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，"cab" 可以写成 "-.-.-....-"，(即"-.-." + "-..." + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。

返回我们可以获得所有词不同单词翻译的数量。

例如:

输入: words =["gin", "zen", "gig", "msg"]

输出: 2

解释:

各单词翻译如下:

"gin"-> "--...-."

"zen"-> "--...-."

"gig"-> "--...--."

"msg"-> "--...--."

共有 2 种不同翻译, "--...-." 和 "--...--.".

注意:

• 单词列表words 的长度不会超过 100。

• 每个单词 words[i]的长度范围为 [1, 12]。

• 每个单词 words[i]只包含小写字母。