проверка количества бит в байтах?

Question

Я знаю, что мы можем установить любой бит в байте с помощью логической операции ИЛИ и может очистить любой бит на логическое И как к

val |= (1<<order_number_of_bit_to_set); //for setting some specific number of bit 

и для очистки немного

val &= ~(1<<order_number_of_bit_to_clear); // specific bit to clear 

но мой вопрос как мы можем проверить, сколько и какие упорядоченные биты номера заданы в байте.

, например, если мы имеем

val = 0x22; 

это означает, что второй и пятый бит установлен в бай

, что является эффективным, быстрым и кратчайшим способом сделать это?

Быстрое решение, которое пришло в голову, - перебрать все биты и проверить их порядок, а также установить запись и отобразить порядок бит.

Но есть ли другой эффективный способ сделать это?

Answer 1

редактировался @ ответ 0x499602D2 в выше:

int pos[sizeof(/* decltype(val) */)]; 
int bits_on = 0; 
for (int i = sizeof(/* decltype(val) */) * CHAR_BIT - 1; --i;) 
{ 
    pos[i] = (val >> i) & 1; 
    if(pos[i]) bits_on++; 
} 

дает общее и положение.

Answer 2

Количество бит бит может быть оптимизировано.

int bits_on(int x) 
{ 
    x = (x & 0x55555555) + ((x>>1) & 0x55555555); 
    x = (x & 0x33333333) + ((x>>2) & 0x33333333); 
    x = (x & 0x0F0F0F0F) + ((x>>4) & 0x0F0F0F0F); 
    x = (x & 0x00FF00FF) + ((x>>8) & 0x00FF00FF); 
    x = (x & 0x0000FFFF) + ((x>>16) & 0x0000FFFF); 
    return x; 
} 

Но позиции должны быть найдены по петле. (это ответы других.)

Answer 3

Вы должны проверить это Built-Ins declarations, вы можете использовать функцию __builtin_popcount (unsigned int x) Возвращает число 1 бит в x.

Answer 4

Вот сочетание двух алгоритмов, которые итерацию столько раз, сколько там установлены биты:

unsigned count_low_zerobits(unsigned n) { 
    static const unsigned MultiplyDeBruijnBitPosition[32] = 
    { 
     0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
     31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
    }; 
    return MultiplyDeBruijnBitPosition[((n & -n) * 0x077CB531U) >> 27]; 
} 

unsigned find_bits(unsigned n, unsigned positions[]) { 
    unsigned c; 
    for (c = 0; n; c++) { 
     unsigned bitnum = count_low_zerobits(n); // get bit number of lowest bit 
     positions[c] = bitnum; // put number to positions array 
     n ^= 1 << bitnum; // use XOR to unset just this one bit 
    } 
    return c; 
} 

Reference для получения дополнительной информации о count_low_zerobits: an answerPosition of least significant bit that is set вопроса.

Функция find_bits затем просто вызывает это, помещает заданную позицию бита в массив результатов и использует его для отмены этого бита, используя побитовое исключение-или.

Наконец, для удобства, кусок уродливой код, который я использовал, чтобы проверить это:

#include <stdio.h> 
#include <stdlib.h> 

int main(void) 
{ 
    unsigned positions[128] = {0}; 
    int testnumber = 4442344; 

    unsigned count = find_bits(testnumber, positions); 

    // non-standard, leaking one-liner for debug purposes, remove if fails to compile: 
    printf ("Number in binary: %s\n", itoa(testnumber, malloc(129), 2)); 

    printf("%u bits: ", count); 
    for(unsigned i = 0 ; i < count ; ++i) { 
     printf("%u ", positions[i]); 
    } 
    printf("\n"); 

    return 0; 
}