Сброс самого значимого бита в слове (int32) [C] - PullRequest
Новая
       14

Сброс самого значимого бита в слове (int32) [C]

4 голосов
/ 16 мая 2011

Как я могу сбросить старший значащий бит слова (например, 0x00556844 -> 0x00156844)? В gcc есть __builtin_clz, но он просто считает нули, что мне не нужно. Кроме того, как я должен заменить __builtin_clz для компилятора msvc или intel c?

Текущий мой код 

 int msb = 1<< ((sizeof(int)*8)-__builtin_clz(input)-1);
 int result = input & ~msb;

ОБНОВЛЕНИЕ: Хорошо, если вы скажете, что этот код довольно быстрый, я спрошу вас, как мне добавить переносимость в этот код? Эта версия для GCC, но MSVC & ICC?

Ответы [ 3 ]

7 голосов
/ 16 мая 2011

Просто округлите до ближайшей степени 2, а затем XOR с исходным значением, например, используя flp2() из Восторг Хакера : 

uint32_t flp2(uint32_t x) // round x down to nearest power of 2
{
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >>16); 
    return x - (x >> 1); 
}

uint32_t clr_msb(uint32_t x) // clear most significant set bit in x
{
    msb = flp2(x);  // get MS set bit in x
    return x ^ msb; // XOR MS set bit to clear it
}
6 голосов
/ 12 августа 2015

Если вы действительно обеспокоены производительностью, лучший способ очистить msb недавно был изменен для x86 с добавлением инструкций BMI.

В сборке x86: 

clear_msb:
    bsrq    %rdi, %rax
    bzhiq   %rax, %rdi, %rax
    retq

Теперьпереписать на C и позволить компилятору испускать эти инструкции, в то же время изящно деградируя для архитектур не-x86 или более старых процессоров x86, которые не поддерживают инструкции BMI.

По сравнению с кодом сборки, версия C действительно уродлива иподробный.Но, по крайней мере, это отвечает цели мобильности.И если у вас есть необходимые аппаратные и компиляторные директивы (-mbmi, -mbmi2) для соответствия, вы вернетесь к прекрасному ассемблерному коду после компиляции.

Как написано, bsr () полагается на GCC / Clangвстроенный.Если вы нацелены на другие компиляторы, вы можете заменить их эквивалентным переносимым кодом C и / или другими встроенными компиляторами. 

#include <inttypes.h>
#include <stdio.h>

uint64_t bsr(const uint64_t n)
{
        return 63 - (uint64_t)__builtin_clzll(n);
}

uint64_t bzhi(const uint64_t n,
              const uint64_t index)
{
        const uint64_t leading = (uint64_t)1 << index;
        const uint64_t keep_bits = leading - 1;
        return n & keep_bits;
}

uint64_t clear_msb(const uint64_t n)
{
        return bzhi(n, bsr(n));
}

int main(void)
{
        uint64_t i;
        for (i = 0; i < (uint64_t)1 << 16; ++i) {
                printf("%" PRIu64 "\n", clear_msb(i));
        }
        return 0;
}

Обе версии сборки и C поддаются естественной замене 32-битными инструкциями, как оригиналбыл задан вопрос.

3 голосов
/ 16 мая 2011

Вы можете сделать 

unsigned resetLeadingBit(uint32_t x) {
    return x & ~(0x80000000U >> __builtin_clz(x))
}

Для MSVC есть _BitScanReverse , что равно 31 -__buildin_clz ().

На самом деле, наоборот, BSR этоестественная инструкция x86 и встроенный gcc реализованы как 31-BSR.

...