给定一个整数,n。反转该数字的位的最快方法是什么?例如,如果 n = 5 (101),则输出应为 2(010)。前缀 0
不被视为逆数。这个问题的独特之处在于,在这里,我们不考虑前缀 0
。
我的方法:
Convert n to binary as a string. For example, if n = 5 then I'll have string, say str, as `101`.
Convert 1 to 0 and 0 to 1 in the string. (output: 010)
Convert resultant binary string to number. (output: 2)
更多输入/输出示例:
Input: 7, Output: 0
Input: 8, Output: 7
Input: 10, Output: 5
Input: 98, Output: 29
正如你所看到的,我的方法看起来很幼稚或者非常低效。有没有更好的方法,通过使用一些位操作操作或任何其他方式更快地获得所需的输出?
注意: n
也可以是负数!对于负数,必须考虑 2 的补码来考虑反转位。
我不要求确切的代码。伪代码或方法会很有帮助。
最佳答案
这个问题与将 n 向上舍入为 2^k-1 形式的最小数的问题是可以相互简化的(具有按位 XOR 指令的开销)。对于 32 位 int n,您可以采用后者的标准 bithacks 之一:
m = n;
m |= m >> 1;
m |= m >> 2;
m |= m >> 4;
m |= m >> 8;
m |= m >> 16;
return m ^ n;
关于algorithm - 反转数字位的最快方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30324738/