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.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.
idea: we only want to flip the lower k bits (k is the bits number of num)
Solution 1: use mask to find the leftmost 1 of num, and then use ~mask to make only the k lowest bits to be 1(k is the bits number of num), and then & ~num to get the result.
class Solution { public: int findComplement(int num) { unsigned mask=INT_MAX; while((mask&num)!=0){ mask= mask << 1; } return (~mask & ~num); } };
Solution 2: the needed mask is (2^(int)log(num))-1=(1<<(int)log(num))-1
class Solution { public: int findComplement(int num) { return ~num & ((1 <<(int)log2(num))-1); } };
- 推荐文章
- 20本最好的Linux免费书籍
- struts2中的constant
- 免费磁盘加密工具 TrueCrypt
- asm视频与键盘处理入门
- ASM调用子过程,传参方式
- HTML <meta> httpequiv Attribute
- Struts2基于注解的Action配置
- jqueryloadmask 遮盖层 jquery loading
- Valve公布了最新的硬件调查结果
- 微软公布《机甲指挥官2》源代码
- CEGUI、LayoutEdit和TextureAtlas
- Starforce(几家欢喜几家愁)
- 转:由一段游戏层代码想到的 (<= 深表认同)
- 麦当劳的骗局
- wxWidgets 2.6.3 has been released
- NaN是什么
- 日本游戏制作人对国内制作人的意见
- 我美丽的Revolution
- 羊皮卷的故事第七章
- 羊皮卷的故事第六章
- 羊皮卷的故事第三章
- 羊皮卷的故事第五章
- 羊皮卷的故事第八章羊皮卷之一
- 羊皮卷的故事第十一章羊皮卷之四
- 羊皮卷的故事第四章
- 羊皮卷的故事第十章羊皮卷之三
- 羊皮卷的故事第九章羊皮卷之二
- 羊皮卷的故事第十二章羊皮卷之五
- POJ3264 Balanced Lineup RMQ
- HDUPattern and Text 枚举