javascript - 隔离最左边的 1 位

Question

我正在搜索有关隔离二进制文件中最右边的内容：

我得到了这个解决方案：

y = x & (-x)

所以 ：

    10111100  (x)
&   01000100  (-x)
    --------
    00000100

但是现在，我想通过找到最左边的数字来找到一个数字的大小（虽然不是符号......）

我如何详细说明我的解决方案以找到最左边的位？

例子 ：

10 111100

0 1000100

Answer 1

没有类似的 O(1) 位技巧来找到数字的大小。许多微处理器指令集包括一个“计算前导零”的特殊指令。C 语言家族中没有这样的运算符为 JavaScript 提供按位功能。

唯一的 O(1) 替代方法是使用Math.floor( Math.log( n ) / Math.LN2 )A quick trial of

for ( var i = 0; i == Math.floor( Math.log( 1<<i ) / Math.LN2 ); ++ i ) ;

i == 31由于<<运算符使用 32 位二进制补码有符号算术，因此给出了结果。

如果你想成为一个纯粹主义者，你可以重复右移一个，即 O(log n)，或者你可以重复右移一个16 >> i，i从 0 到 4，当结果为零时拒绝移位，否则累加16 >> i。即 O(log log N) 其中 N 是 的最大可能值n，这意味着恒定时间，但很可能比 慢Math.log。

O(log log N) 算法的代码：

var mag = function( n ) {
     var acc = 0;
     for ( var i = 16; i; i >>= 1 ) {
         if ( n >> i ) {
             n >>= i;
             acc += i;
         }
     }
     return acc;
};

当然，对于其中任何一个，您必须将结果左移一位以获得“最左边的 1 位”而不是索引。

编辑：注意，log基于的实现返回-Infinity为零，而mag函数返回0，这与它的结果相同1。如果您想考虑不存在最左边 1 位的可能性，最好将其设为特殊情况。

Answer 2

我认为这Math.floor( Math.log( n ) / Math.LN2 )不是 O(1)，因为Math.log它不是基本操作。

因此，遵循定理说你不能得到最左边的 1 位：“一个将单词映射到单词的函数可以用单词并行的加、减、和、或和非指令实现当且仅当结果仅取决于每个输入操作数及其右侧的位。”

这个定理在“Hacker's 的喜悦”（Henry S. Warren, Jr.）一书的第 13 页上。