bit-manipulation - 如何在没有while循环的情况下获得32位整数中最重要的非零字节？

Question

我有一种方法可以使用以下方法提取整数中最重要的非零字节：

private static int getFirstByte(int n)
{
    while (n > 0xFF)
        n >>= 8;

    return n;
}

这种方法存在逻辑问题。整数参数可能是负数，这意味着它会返回传入的数字，这是不正确的。

该方法本身也可能存在问题。它正在使用一个while循环。

有没有办法在没有 while 循环的情况下执行这个逻辑，也可能避免负数的错误返回结果？

Answer 1

不聪明，不优雅 - 但我相信它确实“提取整数中最重要的非零字节......而不使用循环”：

private static int getFirstByte(int n) {
  int i;
  if ((i = n & 0xff000000) != 0)
     return (i >> 24) & 0xff;
  if ((i = n & 0xff0000) != 0)
    return (i >> 16) & 0xff;
  if ((i = n & 0xff00) != 0)
    return (i >> 8) & 0xff;
  // all of the higher bytes are zeroes
  return n;
}

Answer 2

你可以使用log n / log 256……但是你会有一个更大的问题。

Answer 3

我假设通过获取第一个非零值byte，int您的意思是自然的 8 位中断，int而不是动态的 8 位中断。

自然 8 位中断：

00000000|00010110|10110010|11110001==>00010110

动态 8 位中断：

00000000000|10110101|1001011110001==>10110101

这将在没有循环或分支byte的自然 8 位中断处返回第一个非零值。int此代码可能会或可能不会比paulsm4答案更有效。请务必对代码进行基准测试和/或分析以确定最适合您的代码。

Java 代码： ideone link

class Main {
    public static void main(String[] args) {
        int i,j;
        for (i=0,j=1; i<32; ++i,j<<=1) {
          System.out.printf("0x%08x : 0x%02x\n",j,getByte(j));
        }
    }
    public static byte getByte(int n) {
        int x = n; 
        x |=   (x >>>  1);
        x |=   (x >>>  2);
        x |=   (x >>>  4);
        x |=   (x >>>  8);
        x |=   (x >>> 16);
        x -=  ((x >>>  1) & 0x55555555);
        x  = (((x >>>  2) & 0x33333333) + (x & 0x33333333));
        x  = (((x >>>  4) + x) & 0x0f0f0f0f);
        x +=   (x >>>  8);
        x +=   (x >>> 16);
        x &= 0x0000003f;
        x  = 32 - x;     // x now equals the number of leading zeros
        x &= 0x00000038; // mask out last 3 bits (cause natural byte break)
        return (byte)((n&(0xFF000000>>>x))>>>(24-x));
    }
}