algorithm - 查找给定二进制数字设置为 0 的第 N 个数

Question

我正在寻找一种给定目标的算法，返回目标位为 0 的第 N 个数字。

例如，对于n={0,1,2,3}和target=1的输入，输出将是(二进制)

000,001,100,101

Answer 1

只写值N-1 (如果枚举从1开始)二进制，然后插入一个0在所需位置 ( target )。

例如:

 for N=3 and target=1 
 N-1 = 10bin
 inserting 0 in 1-th position gives 
 R = 100b = 4dec

使用位操作:

 NN = N- 1
 Mask = (1 << target) - 1   //like 00000111 for target=3
 NotMask = ~ Mask           //like 11111000 for target=3 
 R = (NN & Mask) | ((NN & NotMask) << 1)

表达式 (NN & Mask)选择目标位右侧的位(将其他位归零)
表达式 (NN & NotMask) << 1选择左边的位，然后将它们移位以释放一个位置用于零目标位