在一定条件下求二元级数中某些N的倍数

Question

有人能帮我找到解决下列编程问题的方法吗？你知道吗

我目前正在使用Python2.7

目标：我试着把一系列的数字加在一起，这样它们的和，当写成二进制数时，是所有1的一系列，是某个数N的倍数

以下是我的一般程序：

（例如） 给定bin（N）[2:]='10011' 我可以保证N的倍数，M，通过适当地左移一些M位。。。你知道吗

使得m+m0+0+0+m0000=m是N的倍数（因为N=2^0+2^1+0+0+2^4）。你知道吗

所以问题归结为求m，使得m是1的级数

但我所有的编码尝试都是垃圾。。。你知道吗

我不想做一个“猜测和检查方法使用%”或任何除法。理想情况下，当答案在将所有m相加后在m的二进制字符串中找到“0”时，该方法会自动更正m，但我对其他想法持开放态度，而且越有效的方法越好。你知道吗

谢谢。你知道吗

Answer 1

理解这样一个问题的最好方法是，用纸和笔来计算m，然后将这个过程机械化。你知道吗

• 假设输入总是奇数（n&1==1），您就知道输出是奇数（m&1==1），因为这是在m*n的最低有效位列中获得1的唯一方法。你知道吗
• 然后迭代执行此任务：
  • 左移输入。你知道吗
  • 决定在m列中应该有1还是0。你知道吗
  • 您希望每列中有奇数个1，以将m*n的值保持为二进制1的字符串
  • 输出1如果是奇数，0如果是偶数。。。你知道吗
  • 别忘了进位：-）

下面是一个示例，将n=13（二进制1101）的位移位值相加，确保最下面的行在每一列中放置一个1。你知道吗

0 0 0 0 0 0 0 0 1 1 0 1   == 1
0 0 0 0 0 0 0 1 1 0 1 0   == 1
0 0 0 0 0 0 0 0 0 0 0 0   == 0
0 0 0 0 0 1 1 0 1 0 0 0   == 1
0 0 0 0 1 1 0 1 0 0 0 0   == 1
0 0 0 1 1 0 1 0 0 0 0 0   == 1
0 0 0 0 0 0 0 0 0 0 0 0   == 0
0 0 0 0 0 0 0 0 0 0 0 0   == 0
1 1 0 1 0 0 0 0 0 0 0 0   == 1
=======================
1 1 1 1 1 1 1 1 1 1 1 1

读取右边的列（从最低有效位到最高有效位），答案是100111011，也就是315。所以13 * 315 == 4095，这是（正确的）二进制1的字符串

我不应该真的为你做作业，但好奇心使我冲出一个快速算法来证明这是可行的。你知道吗

def number_of_ones(stack,column):
    return sum([ (value>>column)&1 for value in stack ])

def most_significant_bit(x):
    return len(bin(x))-2

def get_multiplier(n):
    assert n&1, "Must be an odd number input"
    stack = []
    column = 0
    m = 0
    carry_bit = 0
    while len(stack)==0 or column<most_significant_bit(stack[-1]):
        column_sum = number_of_ones(stack,column) + carry_bit
        if (column_sum&1)==0:
            stack.append(n<<column)
            m += (1<<column)
        # Edited to include bug fix :-)
        carry_bit = column_sum>>1
        column += 1
    return m

附录：根据您的需求，您可能希望输出为m*n。你知道吗

附录2：考虑到问题的格式，我想当然地认为这个算法总是会停止，但我还没有给出一个正式的证明。看看会很有趣的。你知道吗