Z*****Z
发帖数: 723 | 1 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: ZhangBZ (向日葵), 信区: InterviewHackers
标 题: 来个bit题
发信站: BBS 未名空间站 (Fri Jul 2 13:22:29 2010, 美东)
感觉这几个是相关的:
1. Let f(k) = y where k is the y-th number in the increasing sequence of non
-negative integers with the same number of ones in its binary representation
as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6)
= 3 and so on. Given k >= 0, compute f(k).
2. There is a series of numbers in ascending order. All these numbers have t
he sam | Z*****Z
发帖数: 723 | 2 用3去求1、2是不是有点儿傻？
non
representation
6)
t
【在 Z*****Z 的大作中提到】
: 【 以下文字转载自 InterviewHackers 俱乐部 】
: 发信人: ZhangBZ (向日葵), 信区: InterviewHackers
: 标 题: 来个bit题
: 发信站: BBS 未名空间站 (Fri Jul 2 13:22:29 2010, 美东)
: 感觉这几个是相关的:
: 1. Let f(k) = y where k is the y-th number in the increasing sequence of non
: -negative integers with the same number of ones in its binary representation
: as y, e.g. f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 1, f(4) = 3, f(5) = 2, f(6)
: = 3 and so on. Given k >= 0, compute f(k).
: 2. There is a series of numbers in ascending order. All these numbers have t
| p******n
发帖数: 32 | 3 第一题，可以这样来做
以二进制数010001001001为例
1. 用0x80000000每次右移1位遍历整个数。遍历完得到这个数里面1的个数，以及每个1
所在位的index
2. 从最左边的1开始，假设这个1后面全是0，算出比当前这个数小的含有相当个数1的
数目，比如，这个例子中最左边的1在第10位，也就是说最左边这个1 后面有10位，那
么含有4个1的数里面，一定有C(10, 4)（10个里面选3个，3个1可以出现在10位里面的
任意3位）个数比它小。
3. 用和2同样的逻辑对每一个1，算出比这个小的数字的个数。这里，对第二个1，就是
C(6.3)，第三个1，就是C(3, 2), 第四个1就是C(1,1)
4. 把所有的数目加起来就是所有比这个数小的数字的个数。 | Z*****Z
发帖数: 723 | 4 这样做是不是算重了。用你的例子：010001001001
C(10,4) + C(6,3) + C(3,2) + C(1,1)
考虑把原数的最左边的1移到最右边，即：000001001011
这个数在C(10,4)、 C(6,3) 和 C(3,2)里面都被计算了1次
个1
【在 p******n 的大作中提到】
: 第一题，可以这样来做
: 以二进制数010001001001为例
: 1. 用0x80000000每次右移1位遍历整个数。遍历完得到这个数里面1的个数，以及每个1
: 所在位的index
: 2. 从最左边的1开始，假设这个1后面全是0，算出比当前这个数小的含有相当个数1的
: 数目，比如，这个例子中最左边的1在第10位，也就是说最左边这个1 后面有10位，那
: 么含有4个1的数里面，一定有C(10, 4)（10个里面选3个，3个1可以出现在10位里面的
: 任意3位）个数比它小。
: 3. 用和2同样的逻辑对每一个1，算出比这个小的数字的个数。这里，对第二个1，就是
: C(6.3)，第三个1，就是C(3, 2), 第四个1就是C(1,1)
| Z*****Z
发帖数: 723 | 5 可不可以这样想。当所求的数中只有1个1的时候是好办的。
计算010001001001，两种情况：
1、 当最左边的1不动时，右面的3个1只能右移。
2、最左边的1向右移动了至少1位，
那么 f(010001001001) = C(10,4) + f(000001001001) + 1
【在 Z*****Z 的大作中提到】
: 这样做是不是算重了。用你的例子：010001001001
: C(10,4) + C(6,3) + C(3,2) + C(1,1)
: 考虑把原数的最左边的1移到最右边，即：000001001011
: 这个数在C(10,4)、 C(6,3) 和 C(3,2)里面都被计算了1次
:
: 个1
| s***e
发帖数: 793 | 6 no.
C(6,3) does not count 010001001001
C(6,3) count like 010000******
clear
【在 Z*****Z 的大作中提到】
: 这样做是不是算重了。用你的例子：010001001001
: C(10,4) + C(6,3) + C(3,2) + C(1,1)
: 考虑把原数的最左边的1移到最右边，即：000001001011
: 这个数在C(10,4)、 C(6,3) 和 C(3,2)里面都被计算了1次
:
: 个1
| Z*****Z
发帖数: 723 | 7 哦，明白了。我的那个和这个其实是一样的
【在 s***e 的大作中提到】
: no.
: C(6,3) does not count 010001001001
: C(6,3) count like 010000******
: clear
| y****n
发帖数: 579 | 8 第三题碰到不存在的情况怎么办？
像0000 0111 next smallest就不存在。 | x****k
发帖数: 2932 | |
|
