Extrato n mais significativo diferente de zero bits do int em C++, sem loops
-
16-12-2019 - |
Pergunta
Eu quero extrair os n bits mais significativos de um número inteiro em C++ e converter os n bits para um número inteiro.
Por exemplo
int a=1200;
// its binary representation within 32 bit word-size is
// 00000000000000000000010010110000
Agora eu quero extrair os 4 dígitos mais significativos do que a representação, por exemplo,1111
00000000000000000000010010110000
^^^^
e convertê-los novamente para um número inteiro (1001 em decimal = 9).
Como é possível, com uma simples função de c++, sem loops?
Solução
Alguns processadores têm uma instrução para contar o líder binário de zeros de um número inteiro, e alguns compiladores têm instrinsics para permitir que você use essa instrução.Por exemplo, usando o GCC:
uint32_t significant_bits(uint32_t value, unsigned bits) {
unsigned leading_zeros = __builtin_clz(value);
unsigned highest_bit = 32 - leading_zeros;
unsigned lowest_bit = highest_bit - bits;
return value >> lowest_bit;
}
Para simplificar, eu deixei de fora verifica que o número solicitado de bits estão disponíveis.Para o Microsoft do compilador, o intrínseco é chamado de __lzcnt
.
Se o seu compilador não prever que a intrínseca, e você processador não tem uma adequada instrução, uma maneira de contar os zeros rapidamente é com um binário de pesquisa:
unsigned leading_zeros(int32_t value) {
unsigned count = 0;
if ((value & 0xffff0000u) == 0) {
count += 16;
value <<= 16;
}
if ((value & 0xff000000u) == 0) {
count += 8;
value <<= 8;
}
if ((value & 0xf0000000u) == 0) {
count += 4;
value <<= 4;
}
if ((value & 0xc0000000u) == 0) {
count += 2;
value <<= 2;
}
if ((value & 0x80000000u) == 0) {
count += 1;
}
return count;
}
Outras dicas
Não é rápido, mas (int)(log(x)/log(2) + .5) + 1
vai dizer-lhe a posição de o mais significativo diferente de zero bits.Terminar o algoritmo de lá é bastante simples.
Isso parece funcionar (feito em C# com UInt32, em seguida, transportado para desculpas Bjarne):
unsigned int input = 1200;
unsigned int most_significant_bits_to_get = 4;
// shift + or the msb over all the lower bits
unsigned int m1 = input | input >> 8 | input >> 16 | input >> 24;
unsigned int m2 = m1 | m1 >> 2 | m1 >> 4 | m1 >> 6;
unsigned int m3 = m2 | m2 >> 1;
unsigned int nbitsmask = m3 ^ m3 >> most_significant_bits_to_get;
unsigned int v = nbitsmask;
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -((int)v);
if (v>0) c--;
if ((v & 0x0000FFFF) >0) c -= 16;
if ((v & 0x00FF00FF) >0) c -= 8;
if ((v & 0x0F0F0F0F) >0 ) c -= 4;
if ((v & 0x33333333) >0) c -= 2;
if ((v & 0x55555555) >0) c -= 1;
unsigned int result = (input & nbitsmask) >> c;
Eu supor que você quis dizer, usando somente o número inteiro de matemática.
Eu usei algumas código do @OliCharlesworth link, você pode remover as condicionais também usando a LUT de zeros à direita de código lá.