移位操作的反转 - 确定用于生成值的移位计数

Question

我有代码通过左移从初始值 1 生成一个值。在代码的不同点，我知道生成的值并需要计算用于生成该值的移位计数。

换句话说，我需要通过对生成的值执行运算来确定用于生成移位操作结果的移位计数。

是否可以在不使用专用函数的情况下反转基数二变量的移位操作？当移位值 x 和移位操作的结果 z 已知时，我正在寻找移位计数变量 y 的值。

示例：

x << y = z
1 << 6 = 64

z = 64 and x is 1 but what is y???  // how to calculate y, the shift count?

有很多解决方案，包括 log(64)/log(2)，但我必须使用 math.h。我正在寻找某种快速且不需要函数的按位运算。

编辑：感谢您的回答！我的问题得到了回答，没有办法通过简单的操作来解决这个问题，我的编译器没有 CTZ。 BR

Answer 1

假设您从 z = x << y 知道 x 和 z，并且想使用位运算找出 y，一个简单的方法是取 x 并一次移动一位，将结果与 z 进行比较（即，从 y = 0 开始并在每次比较失败后将 y 递增 1）。

edit：另一方面，如果 x 是 1（或者实际上如果 x 设置了最低位），您还可以计算 z 中的尾随零。您的处理器可能只有一条指令，您的 C 编译器可能会将其公开为 non-portable 扩展，例如 __builtin_ctz（您可以考虑使用 pre-processor 在该指令和可移植指令之间切换解决方案）。对于这个问题，还有比普通循环更快、更便携的解决方案——搜索 "count trailing zeroes".

（在 x 没有设置最低位的情况下，可以计算 x 和 z 中的尾随零以找出差异。）

Answer 2

标准 C 中没有单个操作或函数可以计算整数中尾随零的位数。正如其他答案所建议的那样，您可以通过循环一次检查一位来执行这样的计算。但是，如果您需要做很多事情，那么您可能需要更高效的替代方案，例如：

int trailing_zero_bits(uint64_t x) {
    uint64_t bits = ~(uint64_t)0;
    int rval = 0;

    for (int shift = 32; shift; shift >>= 1) {
        bits >>= shift;
        if (!(x & bits)) {
            rval += shift;
            x >>= shift;
        }
    }

    return rval + !x;  // The !x adds 1 if x is zero at this point
}

该循环将精确迭代 6 次，vs. 对于 64 位 bit-at-a-time 替代方案最多 63 次。

当然，可能有系统或 environment-specific 更有效的替代方案。

Answer 3

替代函数的想法可以使用 switch 语句，如下所示：

int trailing_zero_bits(uint64_t x) {
    int iRetVal = 0;

    switch (x & 0x7f) {
    case 2:
        iRetVal = 1;
        break;
    case 4:
        iRetVal = 2;
        break;
    case 8:
        iRetVal = 3;
        break;
    case 16:
        iRetVal = 4;
        break;
    case 32:
        iRetVal = 5;
        break;
    case 64:
        iRetVal = 6;
        break;
    default:
        iRetVal = 0;
    }

    return iRetVal;
}

这可以使用 Duff's Device 压缩为：

int trailing_zero_bits(uint64_t x) {
    int iRetVal = 0;

    switch (x & 0x3f) {
        case 64:  iRetVal++;
        case 32:  iRetVal++;
        case 16:  iRetVal++;
        case 8:  iRetVal++;
        case 4:  iRetVal++;
        case 2:  iRetVal++;
            break;
        default:
            break;
    }

    return iRetVal;
}

或者您可以采用查找 table 方法，如：

int trailing_zero_bits(uint64_t x) {
    unsigned char  x1[9] = { 0, 0, 1, 0, 2, 0, 0, 0, 3 };
    unsigned char  x2[9] = { 0, 4, 5, 0, 6, 0, 0, 0, 0 };

    return x1[x & 0xf] | x2[(x & 0x70) >> 4];
}

或者

int trailing_zero_bits(uint64_t x) {
    unsigned short x1[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40 };
    unsigned short xVal = (unsigned short)(x & 0x7f);
    int  i = 0;

    if (xVal) for (i = 0; (x1[i] & xVal) == 0; i++);

    return i;
}

或用以下方法消除 table：

int trailing_zero_bits(uint64_t x) {
    unsigned short x1 = 0x01;
    unsigned short xVal = (unsigned short)(x & 0x7f);
    int  i = 0;

    if (xVal) for (i = 0; (x1 & xVal) == 0; i++, (x1 <<= 1));

    return i;
}

或回到使用 table 但使用指针来消除索引：

int trailing_zero_bits(uint64_t x) {
    unsigned short x1[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40};
    unsigned short *x2 = x1;
    unsigned short xVal = (unsigned short)(x & 0x7f);

    if (xVal) for ( ; (*x2 & xVal) == 0; x2++);

    return (x2 - x1);
}

移位操作的反转 - 确定用于生成值的移位计数

Invert of a shift operation - determine shift count used to generate value

c

bit-shift