查找给定二进制数字设置为 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 选择左边的位，然后将它们移位以释放一个位置用于零目标位

Answer 2

随着我们向上移动自然数序列，目标位在未设置 target**2 次和设置 target**2 次之间振荡。所以我们可以直接计算目标位未设置的第n个数

JavaScript代码：

function f(n, target){
    let block = 1 << target
    
    if (n < block)
      return n
      
    let index_in_block = n % block;
    let num_set_blocks = (n - index_in_block) / block
      
    return 2 * num_set_blocks * block + index_in_block
}

for (let i=0; i<10; i++)
  console.log(i, f(i, 1))

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

Finding the Nth number where a given binary digit is set to 0

algorithm

bitwise-operators

bit

bit-shift

bits