查找二进制数的组合(匹配 1 的数字)

Question

给定二进制号，要找到所有1个与给定数字对应的所有匹配的二进制数字的算法是什么。

例如：输入：10010输出：[10010，10011，10110，1011，11010，11011，11110，11111]

Answer 1

您也可以使用一些技巧

让我们考虑具有初始值的字节大小变量：
v = 00010010
找到两个的功能：（nb：有更有效的方法）

 b = 1
 while (b <= v)
     b = b << 1

现在b = 00100000
制作蒙版bm = b - 1 = 00011111
反向初始值：
n = not v = 11101101
清晰的领先位：
mask = n & bm = 00001101

此mask值包含我们需要填充的所有位。列举给定位蒙版的所有子掩码有一些窍门：

sub = mask
while (sub) {
    output sub | v
    sub = (sub - 1) & mask;
   //clears LSB, sets trailing 0s, removes bits not presenting in mask
}
output sub | v 

delphi代码：

var
  v, b, bm, n, mask, sub: Byte;
begin
  v := 16 + 2;
  if v < 2 then 
    Exit;
  b := 1;
  while (b <= v) do
     b := b shl 1;
  bm := b - 1;
  n := not v;
  mask := n and bm;
  sub := mask;
  while (sub > 0) do begin
    Writeln(IntToBin(sub or v, 8)); //binary representation
    sub := (sub - 1) and mask;
  end;
  Writeln(IntToBin(sub or v, 8));

输出：

00011111
00011110
00011011
00011010
00010111
00010110
00010011
00010010

Answer 2

答案的提示：您要将1保留在其中。因此，基本上，系统的公认语言为{0}。

解决方案＃1：丑陋的一个

brut-force and，取2^n二进制数，其中n是您的数字的大小。仅保留那些与您的图案匹配的人。

解决方案＃2：简化的一个

再次，您想保留1个位置。因此，您想找到具有模式的所有二进制文件，让我们调用 g 您所有1的位置的集合。strong> i 。

的意思是，您只需要在一个字符表中拿走所有二进制规范 2^（n-i）-1 a在 g 中包含的每个位置的1个位置。

示例：

输入：10010
g = {1,4}（基于0，我们在计算机上）

生成a 2^（n-i）-1 table = [000，001，010，100，100，011，101，110，110，111]

将这些数字放入b（n代表 null ），然后用您的数字替换每个 null ：
第一步：[1NN1N，1NN1N，1NN1N，1NN1N，1NN1N，1NN1N，1NN1N，1NN1N，1NN1N，1NN1N]
第二步：[10010，10011，10110，11010，10111，11010，11110，11111]

注意：

记住这些解决方案是基于字符串的。您可能无法用每种语言实现这些解决方案。如果您需要携带基于算法的位，只需将二进制文件从0到 2^n-1 >或执行或操作。（等于解决方案1的解决方案）