计算 2 的最高次幂以整除 C 中的数字

Question

我需要编写一些逻辑来确定给定偶数。将其平分的两个的最高幂。当输入 % 2^n == 0 时 2^n 的最大值是多少？

即：
输入 -> 输出

4  (0100)  -> 4

8  (1000)  -> 8

12 (1100)  -> 4

14 (1110)  -> 2

24 (11000) -> 8

etc....

看起来有一些按位逻辑可以解决：当查看二进制输入时，最右边的一位似乎是解决方案。在C语言中如何确定这个值？还有其他更容易的解决方案吗？

谢谢- 乔纳森

Answer 1

如果您愿意假设 2 的补码算术：

x & -x

如果您经常做此类事情（或者即使您只是觉得很有趣），请给自己找一本《黑客的乐趣》。

编辑： avakar 正确地指出，如果类型是无符号的，则这不依赖于 2 的补码。标准的相关部分是 §6.2.5，第 9 段：

涉及无符号的计算 操作数永远不会溢出，因为 无法表示的结果 结果无符号整数类型是 对 1 进行模减 大于最大值 可以用结果表示 类型。

“比最大值大”为特别不正当的实现（特别是不使用二进制的实现）留下了一些回旋余地，但你不太可能遇到这种情况。

Answer 2

我们可以将

(-x)

替换为

(~x + 1)

：

x & (~x+1) 

您绝对必须知道的低级位黑客提供了详细的解释。

Answer 3

不使用浮点运算：

((x ^ (x - 1)) >> 1) + 1

简化和边缘情况留给读者作为练习。

Answer 4

2^n 形式的数字以二进制形式表示，即 1 后跟一系列 0 或多个 0。 例如，1、10、100、1000...等都是2的幂。

要获得给定数字除以 2 的最高幂，您可以执行以下两个步骤：

1. 以二进制形式写出该数字。例如，如果数字是 168，则写入 10101000。

2. 划掉右侧第一个包含 1 的位之前的所有位。对于 168，划掉 10101000 的第一部分后剩下的就是 1000（= 十进制的 8）。

剩下的就是你的结果 - 即除该数字的 2 的最高次幂。

以编程方式，让 x 是您输入的数字。那么你想要的输出将是：

x - (x ^ (x-1))

说明：

x ^ (x-1)

[意思是 x XOR x-1] 去掉 LSB（最低有效位）侧的第一个 1

x - (x ^ (x-1))

去掉剩余部分，只保留LSB侧的前1个。

Answer 5

def solution_3(N):
  # Range of the power of 2 that devides integer N
  A = range(0, N)
  # The list to store the values of N modulo 2**k == 0
  list = []
  # For loop to find all the values of k for which N % 2**k == 0
  for k in A:
    if N % 2**k == 0:
      # Append the value of k into the list
      list.append(k)
  return max(list)
  

Answer 6

在 Codility 中实现 100% 回报的简单易行的解决方案

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(N):
    # Implement your solution here
    highest = 0
    for i in range(0,N):
        output = pow(2,i)
        if (N%output==0):
            highest=i
        if output*2>N:
            break
    return(highest)