z*********e
发帖数: 10149 | 1 hackerrank上的，觉得比较有意思，也不难
x和n是2个整数，
0 <= n <= 10^15
0 <= x <= n
两个限制条件
那么对于 n = 90000000000000
有多少个x满足上面2个条件，并且同时满足
x + n = x xor n
xor是整数对应的二进制表示进行bit异或 |
H********g
发帖数: 43926 | |
H********g
发帖数: 43926 | 3 n已经比10^15小了，为啥还要比90000.。。。。小？ |
H********g
发帖数: 43926 | 4 哦是等于900000
【在 H********g 的大作中提到】
: n已经比10^15小了，为啥还要比90000.。。。。小？
|
H********g
发帖数: 43926 | 5 那题目不就是
0<=x<=90000000000000
x + 90000000000000 = x xor 90000000000000
问有多少个x？ |
z*********e
发帖数: 10149 | 6 是，其实这个n可以非常大，
而且这个题目是可以手算的！当然9*10^14比较大，会比较繁琐，假如n = 9000，那么
手算就不是那么复杂了
n给的比较大主要怕你们for x = 1: n
【在 H********g 的大作中提到】
: 那题目不就是
: 0<=x<=90000000000000
: x + 90000000000000 = x xor 90000000000000
: 问有多少个x？
|
H********g
发帖数: 43926 | 7 0+0=0=0xor0
1+0=1=1xor0
1+1=10=1xor1+10
如果n的某位上是0，它加同一位上的0或1 都等于异或0 或者1，并且不产生进位
如果n的某位上是1，它加同一位上的1或0 仍旧等于异或0或者1，但是加1之后有进位，
会翻转高位的结果。
所以当n某位有1，x的某位也有1的时候，n+x<>x xor n
而除了0之外，一个数字最高位总是1。因此符合条件的数字必然最高位的1在
90000000000的2进制数里有0的地方。一个数字的最高位在n的某位是1的地方，那它肯
定就不行，不管低位是多少。
(90000000000000)10 = (10100011101101011000010000001111010000000000000)2
所以以下数字都是不行的（x是0或者1）
10100011101101011000010000001111010000000000000
0000000000000000000000000000000001xxxxxxxxxxxxx
（有00000000000000000000000000000000001000000000000个，下同 ）
00000000000000000000000000000001xxxxxxxxxxxxxxx
0000000000000000000000000000001xxxxxxxxxxxxxxxx
000000000000000000000000000001xxxxxxxxxxxxxxxxx
00000000000000000000000000001xxxxxxxxxxxxxxxxxx
0000000000000000000001xxxxxxxxxxxxxxxxxxxxxxxxx
00000000000000001xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
00000000000001xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
000000000001xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
000000001xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
00000001xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
0000001xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
001xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
1xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
(<(90000000000000)10 ，）
前面15行一共
00100011101101011000010000001111010000000000000个（后面15个1）
最后一行这些有
10100011101101011000010000001111010000000000000-
10000000000000000000000000000000000000000000000+1
=
00100011101101011000010000001111010000000000001个
所有这些不行的加起来总数应该是
00100011101101011000010000001111010000000000000+
00100011101101011000010000001111010000000000001
=
01000111011010110000100000011110100000000000001
所以可以的x是
10100011101101011000010000001111010000000000000-
00100011101101011000010000001111010000000000000-
00100011101101011000010000001111010000000000001
=
10000000000000000000000000000000000000000000000-
00100011101101011000010000001111010000000000001
=
01011100010010100111101111110000101111111111111
=50737488355327 |
z*********e
发帖数: 10149 | 8 分析的大方向差不多，细节上有点问题，结果不对
【在 H********g 的大作中提到】
: 0+0=0=0xor0
: 1+0=1=1xor0
: 1+1=10=1xor1+10
: 如果n的某位上是0，它加同一位上的0或1 都等于异或0 或者1，并且不产生进位
: 如果n的某位上是1，它加同一位上的1或0 仍旧等于异或0或者1，但是加1之后有进位，
: 会翻转高位的结果。
: 所以当n某位有1，x的某位也有1的时候，n+x<>x xor n
: 而除了0之外，一个数字最高位总是1。因此符合条件的数字必然最高位的1在
: 90000000000的2进制数里有0的地方。一个数字的最高位在n的某位是1的地方，那它肯
: 定就不行，不管低位是多少。
|
H********g
发帖数: 43926 | 9 我也看出来错了，正在从新算
【在 z*********e 的大作中提到】
: 分析的大方向差不多，细节上有点问题，结果不对
|
z*********e
发帖数: 10149 | 10 可以先不用考虑这么的大的数字，50-100这样的都可以，容易看清楚问题
【在 H********g 的大作中提到】
: 我也看出来错了，正在从新算
|
|
|
H********g
发帖数: 43926 | 11 应该这样
10100011101101011000010000001111010000000000000
第一系列
00000000000000000000000000000000001xxxxxxxxxxxx 12个x
共
00000000000000000000000000000000000100000000000个 =2exp11个
第二系列：
0000000000000000000000000000000010xxxxxxxxxxxxx 12个x
共
00000000000000000000000000000000001000000000000个 =2exp11个
个
第三系列
00000000000000000000000000010000x0xxxxxxxxxxxxx 13个x
共
00000000000000000000000000000000001000000000000 x2个 =2exp12个
第四系列
000000000000000000000000001x0000x0xxxxxxxxxxxxx 14个x
共
00000000000000000000000000000000001000000000000 x2x2个=2exp13个
第五系列
00000000000000000000000001xx0000x0xxxxxxxxxxxxx 15个x
共
00000000000000000000000000000000001000000000000 x2x2x2个 =2exp14个
所以：假如把最高位的1放在从右边数第m个0上，
它带的所有可以用的数字是2exp（m-1）个
另外还有个0也是符合条件的。
n里一共31个0。
所以
总数是
sum（1..31）（2exp （m-1）)+1
=11111 11111 11111 11111 11111 11111 +1
=100000 00000 00000 00000 00000 00000
=2exp31 |
f***n
发帖数: 4682 | 12 小于10^15并且最高为是0（二进制）数的个数
瞎猜的 |
c*******t
发帖数: 1095 | 13 Xor 就是不进位的加法。所以n转成二进制有m个0，答案是2^m
【在 H********g 的大作中提到】
: 应该这样
: 10100011101101011000010000001111010000000000000
: 第一系列
: 00000000000000000000000000000000001xxxxxxxxxxxx 12个x
: 共
: 00000000000000000000000000000000000100000000000个 =2exp11个
: 第二系列：
: 0000000000000000000000000000000010xxxxxxxxxxxxx 12个x
: 共
: 00000000000000000000000000000000001000000000000个 =2exp11个
|
H********g
发帖数: 43926 | 14 你是对的。我用笨办法折腾半天就是这个答案。
【在 c*******t 的大作中提到】
: Xor 就是不进位的加法。所以n转成二进制有m个0，答案是2^m
|
z*********e
发帖数: 10149 | 15 我在看你的解释
结果还是不对
【在 H********g 的大作中提到】
: 应该这样
: 10100011101101011000010000001111010000000000000
: 第一系列
: 00000000000000000000000000000000001xxxxxxxxxxxx 12个x
: 共
: 00000000000000000000000000000000000100000000000个 =2exp11个
: 第二系列：
: 0000000000000000000000000000000010xxxxxxxxxxxxx 12个x
: 共
: 00000000000000000000000000000000001000000000000个 =2exp11个
|
H********g
发帖数: 43926 | 16 我又改了一下，开始数个数有问题
【在 z*********e 的大作中提到】
: 我在看你的解释
: 结果还是不对
|
z*********e
发帖数: 10149 | 17 这个是正解，发个包子鼓励!
解释下，如果n的二进制某一位为0,那么x对应的那个digit可以是0或者1,如果n的某一
位是1,那么x对应的那一位只能为0。所以答案是2^m
【在 c*******t 的大作中提到】
: Xor 就是不进位的加法。所以n转成二进制有m个0，答案是2^m
|
f***n
发帖数: 4682 | 18 也发个包子给我吗？
【在 z*********e 的大作中提到】
: 这个是正解，发个包子鼓励!
: 解释下，如果n的二进制某一位为0,那么x对应的那个digit可以是0或者1,如果n的某一
: 位是1,那么x对应的那一位只能为0。所以答案是2^m
|
