693.交替位二进制数

LeetCode LeetCode 位运算

发布时间 : 2000-01-10 06:09

字数:1.1k 阅读 :

评论:

693.交替位二进制数

693.交替位二进制数

693.1 题目

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2：

输入：n = 7
输出：false
解释：7 的二进制表示是：111

示例 3：

输入：n = 11
输出：false
解释：11 的二进制表示是：1011

提示：

1 <= n <= 2^31 - 1

693.2 题解

位运算判断相邻位是否相同

// 方法一：位运算判断相邻位是否相同
static bool HasAlternatingBits1(int n)
{
    // 使用异或运算判断相邻位是否相同
    // 如果 n 和 n 右移一位的结果进行异或运算得到的结果，再加一，结果为2的幂，则返回 true，否则返回 false
    // n 如果相邻为是交替的 n ^ (n >> 1)得到的是全是1   比如 101  010 异或后变成111
    // 全是1的数+1 得首位为1 后面都是0 111 + 1  1000
    // 在做与全是1的数与 应该是0  000
    return ((n ^ (n >> 1)) + 1 & n) == 0;

    // 这种也可以
    int a = n ^ (n >> 1);
    return (a & (a + 1)) == 0;
}

遍历检查相邻位是否相同

// 方法二：遍历检查相邻位是否相同
static bool HasAlternatingBits2(int n)
{
    // 将 n 转换为二进制字符串
    string binary = Convert.ToString(n, 2);

    // 遍历二进制字符串，检查相邻位是否相同
    for (int i = 1; i < binary.Length; i++)
    {
        // 如果相邻位相同，则返回 false
        if (binary[i] == binary[i - 1])
        {
            return false;
        }
    }

    // 如果所有相邻位都不相同，则返回 true
    return true;
}

693.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

        // 示例 1：
        // 输入：n = 5
        // 输出：true
        // 解释：5 的二进制表示是：101

        // 示例 2：
        // 输入：n = 7
        // 输出：false
        // 解释：7 的二进制表示是：111

        // 示例 3：
        // 输入：n = 11
        // 输出：false
        // 解释：11 的二进制表示是：1011

        // 提示：
        // 1 <= n <= 2^31 - 1

        #endregion

        #region 测试

        // 示例 1
        int n1 = 5;
        bool result1_1 = HasAlternatingBits1(n1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        bool result1_2 = HasAlternatingBits2(n1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int n2 = 7;
        bool result2_1 = HasAlternatingBits1(n2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        bool result2_2 = HasAlternatingBits2(n2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int n3 = 11;
        bool result3_1 = HasAlternatingBits1(n3);
        Console.WriteLine($"示例3 方法1 输出：{result3_1}");
        bool result3_2 = HasAlternatingBits2(n3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        #endregion
    }

    #region 答案

    // 方法一：位运算判断相邻位是否相同
    static bool HasAlternatingBits1(int n)
    {
        // 使用异或运算判断相邻位是否相同
        // 如果 n 和 n 右移一位的结果进行异或运算得到的结果，再加一，结果为2的幂，则返回 true，否则返回 false
        // n 如果相邻为是交替的 n ^ (n >> 1)得到的是全是1   比如 101  010 异或后变成111
        // 全是1的数+1 得首位为1 后面都是0 111 + 1  1000
        // 在做与全是1的数与 应该是0  000
        return ((n ^ (n >> 1)) + 1 & n) == 0;
        
        // 这种也可以
        int a = n ^ (n >> 1);
        return (a & (a + 1)) == 0;
    }

    // 方法二：遍历检查相邻位是否相同
    static bool HasAlternatingBits2(int n)
    {
        // 将 n 转换为二进制字符串
        string binary = Convert.ToString(n, 2);

        // 遍历二进制字符串，检查相邻位是否相同
        for (int i = 1; i < binary.Length; i++)
        {
            // 如果相邻位相同，则返回 false
            if (binary[i] == binary[i - 1])
            {
                return false;
            }
        }

        // 如果所有相邻位都不相同，则返回 true
        return true;
    }

    #endregion
}

693.4 运行结果

示例1 方法1 输出：True
示例1 方法2 输出：True
示例2 方法1 输出：False
示例2 方法2 输出：False
示例3 方法1 输出：False
示例3 方法2 输出：False

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com