找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法题——(位运算)什么时候x xor y == x + y

admin 2019-9-11 19:34 107人围观 C++相关

问题:给定一个正整数x (1 <= x <= 10 ^ 9), 问有几个正整数y, 满足0 < y < x, 并且x xor y == x + y。 其中xor表示按位异或。即0 xor 0 = 1 xor 1 = 0, 1 xor 0 = 0 xor 1 = 1。

例如:

x = 2, 输出1, 只有{1}满足条件。

x = 3, 输出0, 没有数满足条件

x = 4, 输出3, {1, 2, 3}都满足条件。

分析:其实这个题不难。我们用二进制表示x。



(1) x的最高位(bit)是1

(2)满足条件的y,在x为1的那些位(bit)必须是0——因为xor是“没有进位”的加法,我们必须保证x + y在x为1的那些位(bit)没有进位。

注意(2)自然而然的满足了y < x,因为y在x的最高位是0了。

于是,假设x一共有total位(bit),其中为1的为有num位(bit),则答案实际上是2 ^ (total - num) - 1, 即在x中为0 的那些位(bit)自由选择1或者0,而x位1的那些位(bit)必须是0。减1是因为去掉y == 0的非法解。

代码:
    intsolution(int x) {int num = 0, total = 0;while (x) { ++total; num += x & 1; x >>= 1; }return (1 << (total - num)) - 1;}

    ----------------------------------------------------------------------------------------------------------------------
    我们尊重原创,也注重分享,文章来源于微信公众号:程序员算法面试,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
    ----------------------------------------------------------------------------------------------------------------------

    鲜花

    握手

    雷人

    路过

    鸡蛋

    yafeilinux和他的朋友们微信公众号二维码

    微信公众号

    专注于Qt嵌入式Linux开发等。扫一扫立即关注。

    Qt开源社区官方QQ群二维码

    QQ交流群

    欢迎加入QQ群大家庭,一起讨论学习!

    我有话说......