C# obtenir 4 bits supérieurs de uint32 en commençant par le premier bit significatif

Question

Mon besoin est - avoir un certain nombre aléatoire (en fait pseudo) de uint32, j'ai besoin de ses 4 premiers bits indiquant avec le premier bit, qui dans non 0, par exemple.

000100101 ... => 1001

1000 ... 0001 => 1000

... 0001 => 0001

... 0000 => 0000

etc Je comprends que je dois utiliser quelque chose comme ça

uint num = 1157 (some random number) 
uint high = num >> offset 

Le problème est - je ne sais pas où le premier bit est donc je ne peux pas utiliser >> avec variable constante. Quelqu'un peut-il expliquer comment trouver ce offset?

Answer 1

Vous pouvez d'abord calculer le bit le plus fort (HSB), puis décaler en conséquence. Vous pouvez cela comme:

int hsb = -4; 
for(uint cnum = num; cnum != 0; cnum >>= 1, hsb++); 
if(hsb < 0) { 
    hsb = 0; 
} 
uint result = num >> hsb; 

Nous avons donc d'abord pour objectif de détecter l'indice du bit de jeu le plus élevé (ou l'indice moins quatre). Nous faisons cela en incrémentant hsb et en déplaçant cnum (une copie de num) vers la droite, jusqu'à ce qu'il n'y ait plus de bits définis dans cnum.

Ensuite, nous nous assurons qu'il y a un tel bit de consigne et qu'il a au moins quatre index (sinon, rien n'est fait). Le résultat est le num original décalé vers la droite par celui hsb.

Si je lance ceci sur 0x123, je reçois 0x9 dans le csharp shell interactif:

csharp> uint num = 0x123; 
csharp> int hsb = -4; 
csharp> for(uint cnum = num; cnum != 0; cnum >>= 1, hsb++); 
csharp> if(hsb < 0) { 
     >  hsb = 0; 
     > } 
csharp> uint result = num >> hsb; 
csharp> result 
9 

0x123 est 0001 0010 0011 en binaire. Alors:

0001 0010 0011 
    1 001

Et 1001 est 9.

Answer 2

L'un des inconvénients fondamentaux de mes précédentes éditions de cette réponse était le manque de considération pour l'endianness. Cette solution devrait (en théorie) être optimisée par le compilateur en un bitshift approprié pour l'architecture sur laquelle vous travaillez.

if(i == 0) 
    return 0; 

while(num < 128) 
    num *= 2; 

return num >> 28; 

Answer 3

La détermination de la position du bit le plus significatif non nul est le même que le calcul du logarithme de base 2. Il y a des « tours de décalage de bits » pour le faire rapidement sur un processeur moderne:

int GetLog2Plus1(uint value) 
{ 
    value |= value >> 1; 
    value |= value >> 2; 
    value |= value >> 4; 
    value |= value >> 8; 
    value |= value >> 16; 
    value -= value >> 1 & 0x55555555; 
    value = (value >> 2 & 0x33333333) + (value & 0x33333333); 
    value = (value >> 4) + value & 0x0F0F0F0F; 
    value += value >> 8; 
    value += value >> 16; 
    value &= 0x0000003F; 
    return (int) value; 
} 

Cela renverra un nombre de 0 à 32:.

 
Value          + Log2 + 1 
-------------------------------------------+--------- 
0b0000_0000_0000_0000_0000_0000_0000_0000U |  0 
0b0000_0000_0000_0000_0000_0000_0000_0001U |  1 
0b0000_0000_0000_0000_0000_0000_0000_0010U |  2 
0b0000_0000_0000_0000_0000_0000_0000_0011U |  2 
0b0000_0000_0000_0000_0000_0000_0000_0100U |  3 
... 
0b0111_1111_1111_1111_1111_1111_1111_1111U |  31 
0b1000_0000_0000_0000_0000_0000_0000_0000U |  32 
0b1000_0000_0000_0000_0000_0000_0000_0001U |  32 
...          | 
0b1111_1111_1111_1111_1111_1111_1111_1111U |  32 

(tatillons Math remarquerez que le logarithme de 0 est indéfini Cependant, j'espère que le tableau ci-dessus montre comment cela est géré et a un sens pour ce problème.)

Vous pouvez ensuite calculer les bits les plus significatifs non nuls en tenant compte du fait que vous voulez que les 4 bits les moins significatifs si la valeur est inférieure à 8 (où log2 + 1 est < 4):

var log2Plus1 = GetLog2Plus1(value); 
var bitsToShift = Math.Max(log2Plus1 - 4, 0); 
var upper4Bits = value >> bitsToShift;