前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode笔记:693. Binary Number with Alternating Bits

LeetCode笔记:693. Binary Number with Alternating Bits

作者头像
Cloudox
发布2021-11-23 16:39:24
1790
发布2021-11-23 16:39:24
举报
文章被收录于专栏:月亮与二进制月亮与二进制

问题(Easy):

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values. Example 1: Input: 5 Output: True Explanation: The binary representation of 5 is: 101 Example 2: Input: 7 Output: False Explanation: The binary representation of 7 is: 111. Example 3: Input: 11 Output: False Explanation: The binary representation of 11 is: 1011. Example 4: Input: 10 Output: True Explanation: The binary representation of 10 is: 1010.

大意:

给出一个正整数,检查其是否有交替的比特位:也就是说,如果相邻的两个比特位始终有不同的值。 例1: 输入:5 输出:True 解释: 5的二进制表示是:101 例2: 输入:7 输出:False 解释: 5的二进制表示是:111 例3: 输入:11 输出:False 解释: 5的二进制表示是:1011 例4: 输入:10 输出:True 解释: 5的二进制表示是:1010

思路:

最简单的就是循环右移并用模2来获得最低位的值,并依次进行比较看是否不同。

代码(C++):

代码语言:javascript
复制
class Solution {
public:
    bool hasAlternatingBits(int n) {
        int temp = n % 2;
        while (n > 0) {
            n = n >> 1;
            if (n % 2 == temp) return false;
            temp = n % 2;
        }
        return true;
    }
};

他山之石:

交替的比特位其实是个很有特点的排列,如果右移一次,得到的数可以刚好和原本的数互补,比如101010,右移得到10101:

101010 010101

相加就会得到:

11111

我们可以利用这个特点,如果是交替的比特位,右移一位后相加可以得到一个全是1的数,再加1会的得到一个最高位为1,其余位为0的数,与全是1的数相与将为0,但如果不是交替的比特位,就没有这个特性,因此可以这样判断,速度更快。

代码语言:javascript
复制
class Solution {
public:
    bool hasAlternatingBits(int n) {
        return (((long)n + (n>>1) + 1) & ((long)n + (n>>1))) == 0;
    }
};

合集:https://github.com/Cloudox/LeetCode-Record


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018/1/13 上,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题(Easy):
  • 大意:
  • 思路:
  • 代码(C++):
  • 他山之石:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档