Инвертировать операцию сдвига - определить количество сдвигов, используемых для генерации значения

Question

У меня есть код, который генерирует значение из начального значения 1, используя сдвиг влево. В другом месте кода я знаю сгенерированное значение, и мне нужно вычислить число сдвигов, использованное для генерации значения.

Другими словами, мне нужно определить число сдвигов, используемых для генерации результата операции сдвига, выполнив операцию над сгенерированным значением.

Можно ли инвертировать операцию сдвига переменной base 2 без использования выделенной функции? Я ищу значение переменной счетчика сдвигов y, когда смещенное значение x и результат операции сдвига z известны.

Пример:

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

В стандарте 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 раз, против вверхв 63 раза для 64-битной альтернативы.

Конечно, могут быть альтернативы, зависящие от системы или среды, которые еще более эффективны.

Answer 2

Альтернативные идеи функций могут использовать оператор переключения, как в:

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;
}

И это можно сжать, используя Устройство Даффа до:

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;
}

ИлиВы могли бы использовать подход таблицы поиска, как в:

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;
}

Или исключить таблицу с помощью:

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;
}

Или вернуться к использованиютаблица, но с указателями для исключения индексации:

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);
}

Answer 3

Предполагая, что вы знаете x и z из z = x << y и хотите узнать y, используя побитовые операции, простым способом было бы взять x и сдвигать его по одному за раз, сравниваярезультат до z (т. е. начинать с y = 0 и увеличивать y на единицу после каждого неудачного сравнения).

edit : с другой стороны, если xравен 1 (или действительно, если x имеет самый низкий установленный бит), вы также можете посчитать конечные нули в z.Ваш процессор может иметь для этого одну инструкцию, которую ваш компилятор C может представить как непереносимое расширение, например __builtin_ctz (вы можете рассмотреть возможность использования препроцессора для переключения между этим и переносимым решением).Существуют также более быстрые, портативные решения этой проблемы, чем простой цикл - поиск «счетчика завершающих нулей».

(В случаях, когда x не имеет установленного младшего бита, можно посчитать конечные нулив обоих x и z, чтобы выяснить разницу.)