Dernier " n " bits unsigned int

Comment définir (dans la plupart de manière élégante) exactement n bits de poids faible de uint32_t? C'est-à-écrire une fonction void setbits(uint32_t *x, int n);. La fonction doit gérer chaque n de 0 à 32.

Surtout de la valeur n==32 doivent être manipulés.

en dernière voulez-vous dire d'ordre élevé ou faible?
cette question gère toutes les valeurs dans l'intervalle [0, 64]: Créer un masque avec N bits de poids faible set

InformationsquelleAutor Cartesius00 | 2011-11-14

bitwise-operators c c++gcc

20

Si vous voulez dire le moins significatif n bits:
```
((uint32_t)1 << n) - 1
```
Sur la plupart des architectures, cela ne marchera pas, si n est de 32, de sorte que vous pourriez avoir à faire un cas particulier pour que:
```
n == 32 ? 0xffffffff : (1 << n) - 1
```
Sur une architecture 64 bits, un (probablement) solution plus rapide consiste à jeter vers le haut puis vers le bas:
```
(uint32_t)(((uint64_t)1 << n) - 1)
```
En fait, cela pourrait même être plus rapide sur une architecture 32 bits, car elle évite la ramification.
- Ce sujet n==32?
- Oui, ça fonctionne parfaitement! Provoquer 0 - 1 = 0xFFFFFFFF.
- Bon point. J'ai modifié ma réponse.
- Je suppose que ça fonctionne même sans u64 test, il suffit de la première version, n'est-ce pas?
- Non, ça ne fonctionne pas, car la vitesse d'un entier de 32 bits en 32 bits n'est pas pris en charge sur la plupart des architectures (certainement pas sur Intel).
- À droite: "Le comportement est indéfini si l'opérande de droite est...égal à la longueur en bits de l'promu opérande de gauche." [C++11 §5.8/1]
- n == 32 se déplace d'un passé la largeur, ce qui est un comportement indéfini.
- De toute façon, Marcelo, réponse acceptée. Bon à savoir sur 1<<32 question.
- ((uint32_t)-1)>>(32-n) 😉
- Je ne pense pas que cette réponse est correcte. 1 est de type int et 1 << n qui pourrait aller mal pour beaucoup plus de cas que vous ne le supposez. Un premier coup serait d'utiliser 1U << n mais alors l'OP explicitement voulu uint32_t. Pour que la bonne chose serait d'utiliser UINT32_C(1) << n.
- Nice. Bien que je suppose que vous vouliez dire (uint32_t)((-1)>>(32-n))
- oups. Mais non, je voulais dire (uint32_t), signé il va rester avec tous les bits définis pour toutes les valeurs de n.
- Je vois que vous avez édité votre supposition, pas encore, je veux la lancer, avant de passer.
- Mais oui, 32 bits maj ne fonctionne pas.
- Autres que 32, qui a déjà été abordé, que les autres / les valeur(s) n'est pas de ma réponse, gérer correctement?
- Ah, désolé, j'ai mal compris ce que vous essayiez de le faire. Oui, ça marche, mais il a aussi un bord-cas: n == 0.
- IRC maj gauche avec 31 sur un entier de 32 bits, conduit à débordement => un comportement indéfini. Et puis int n'est garanti que pour être de 16 bits de large par la norme. En résumé votre version peut échouer pour des valeurs de 16 à 31.
- aussi en version plus rapide, quel est le but de la fonte n à uint64_t? Vous devez "fonte" la 1 c'est ce qui détermine le type de l'expression.
- La ramification serait probablement pas être un problème ici... il y a des instructions de montage spécifiques à traiter le plus simple cond?a:b les cas de ce genre. Essayez de compiler en assemblée et vérification de la sortie.
- Ah oui, de bons points, j'ai corrigé. Quand vous avez dit, "beaucoup plus de cas", je pensais que vous parliez de quelque chose de plus calamiteuse.
- au moins le 31 est calamiteuse. Veuillez les corriger par juste de mettre un 1U au lieu de 1 comme base de la maj.
- Vous pouvez simplement utiliser ~0UUL ou ~0UL au lieu de 0xsomanyf. Ça va être plus indépendant de la plateforme que vous n'avez pas besoin de connaître la taille exacte de int ou long ou quoi que ce soit.
- L'OP stipulé uint32_t.
- Si vous ne pouvez pas transférer tout le chemin à travers, puis faites demi de cela, et puis faire le reste: (1 << n/2 << n - n/2) - 1 (une sorte de blague)
- il existe de nombreuses façons de gérer ce cas, sans une branche: Créer un masque avec N bits de poids faible set
InformationsquelleAutor Marcelo Cantos
17

Voici une méthode qui ne nécessite pas d'arithmétique:
```
~(~0u << n)
```
- +1, pas d'accès à la mémoire, pas de branches et pas des cas particuliers. Je considère que cela est la solution la plus élégante.
- Sauf que c'est (parfois) échoue pour n = 32, puisque la vitesse d'un uint_32t par 32 est un comportement indéterminé.
InformationsquelleAutor Eric
10

Les autres réponses ne gèrent pas le cas spécial de n == 32 (décalage par supérieure ou égale à la type largeur de l'UB), voici donc une meilleure réponse:
```
(uint32_t)(((uint64_t)1 << n) - 1)
```
Sinon:
```
(n == 32) ? 0xFFFFFFFF : (((uint32_t)1 << n) - 1)
```
- Les autres réponses gérer parfaitement. (1 << 32) - 1 est 0xFFFFFFFF.
- Non, ils ne le font pas. Déplacement au-delà de la longueur du type n'est pas défini.
- Vous êtes downvoting parce que j'ai donné une réponse contenant un code portable avec bien défini de comportement?
- Aussi, il ne fonctionne pas sur x86 avec GCC 4.1.2.
- Cela a autant à voir avec le CPU que le compilateur, et il ne fonctionne pas de mon i686-apple-darwin11-llvm-gcc-4.2.
- casting d'une constante? Ce devrait juste être UINT64_C(1). Et puis, votre solution ne fonctionne pas sur des architectures avec 16 bits int, mais ne fonctionne pas pour la version 32 bits int soit, parce que pour 31 vous avez un dépassement de capacité.
- Quel est le problème avec (uint64_t)1?
- pourquoi le moulage d'un constant où la langue vous donne le droit de l'outil d'indiquer seulement le droit?
InformationsquelleAutor Oliver Charlesworth
5
```
const uint32_t masks[33] = {0x0, 0x1, 0x3, 0x7 ...

void setbits(uint32_t *x, int n)
{
   *x |= masks[n];
}
```
- Inutile quantités de codage, mais au moins il donnera la bonne réponse.
- Je suppose quantité inutile d'accès à la mémoire.
InformationsquelleAutor TJD
1

Si tu veux dire que le plus important n bits:
```
-1 ^ ((1 << (32 - n)) - 1)
```
InformationsquelleAutor anonymous coward

Si n est égal à zéro alors pas de bits doivent être fixés sur la base de la question.

const uint32_t masks[32] = {0x1, 0x3, 0x7, ..., 0xFFFFFFFF};

void setbits(uint32_t *x, int n)
{
    if ( (n > 0) && (n <= 32) )
    {
        *x |= masks[--n];
    }
}

InformationsquelleAutor Jim Rhodes

1

Objectifs:
- pas de succursales (y compris la vérification des paramètres de n)
- pas de 64 bits conversions
```
void setbits(uint32_t *x, unsigned n) {
    //As @underscore_d notes in the comments, this line is
    //produces Undefined Behavior for values of n greater than
    //31(?). I'm ok with that, but if you're code needs to be
    //100% defined or you're using some niche, little-used
    //compiler (perhaps for a microprocesser?), you should
    //use `if` statements. In fact, this code was just an
    //an experiment to see if we could do this in only 32-bits
    //and without any `if`s. 
    *x |= (uint32_t(1) << n) - 1;
    //For any n >= 32, set all bits. n must be unsigned
    *x |= -uint32_t(n>=32);
}
```
Remarque: si vous avez besoin d' n pour être de type int, ajoutez ceci à la fin:
```
    //For any n<=0, clear all bits
    *x &= -uint32_t(n>0);
```
Explication:
```
    *x |= -uint32_t(n>=32);
```
Quand n>=32 est vrai, x sera au niveau du bit-par un ou binaire avec 0xFFFFFFFF, ce qui donne un x avec tous les bits définis.
```
    *x &= -uint32_t(n>0);
```
Cette ligne indique qu'aussi longtemps que les bits doivent être fixées, n>0, au niveau du bit ET x avec 0xFFFFFFFF qui n'apportera aucun changement à x. Si n<=0, x sera au niveau du bit-ANDed avec 0 et, donc, une valeur de 0.

Exemple de programme pour montrer que l'algorithme fonctionne:
```
#include <stdio.h>
#include <stdint.h>

void print_hex(int32_t n) {
  uint32_t x = (uint32_t(1) << n);
  printf("%3d:  %08x  |%08x  |%08x  &%08x\n",
         n, x, x - 1,
         -uint32_t(n>=32),
         -uint32_t(n>0));
}

void print_header() {
  //       1:  00000002  |00000001  |00000000  &ffffffff
  printf("  n:   1 << n    (1<<n)-1   n >= 32     n <= 0\n");
}

void print_line() {
  printf("---------------------------------------------\n");
}

int main() {
  print_header();
  print_line();
  for (int i=-2; i<35; i++) {
    print_hex(i);
    if (i == 0 || i == 31) {
      print_line();
    }
  }
  return 0;
}
```
De sortie (cassé et annoté):

Pour n < = 0, la dernière étape de l'ANDs avec 0 garantir le résultat est 0.
```
  n:   1 << n    (1<<n)-1   n >= 32     n <= 0
---------------------------------------------
 -2:  40000000  |3fffffff  |00000000  &00000000
 -1:  80000000  |7fffffff  |00000000  &00000000
  0:  00000001  |00000000  |00000000  &00000000
```
Pour 1 <= n <= 31, les deux dernières étapes "OU 0, ET la valeur 0xffffffff" provoque aucun changement à ce numéro. La seule étape qui compte, c'est le "OU (1<
```
  n:   1 << n    (1<<n)-1   n >= 32     n <= 0
---------------------------------------------
1:  00000002  |00000001  |00000000  &ffffffff
2:  00000004  |00000003  |00000000  &ffffffff
3:  00000008  |00000007  |00000000  &ffffffff
4:  00000010  |0000000f  |00000000  &ffffffff
5:  00000020  |0000001f  |00000000  &ffffffff
6:  00000040  |0000003f  |00000000  &ffffffff
7:  00000080  |0000007f  |00000000  &ffffffff
8:  00000100  |000000ff  |00000000  &ffffffff
9:  00000200  |000001ff  |00000000  &ffffffff
10:  00000400  |000003ff  |00000000  &ffffffff
11:  00000800  |000007ff  |00000000  &ffffffff
12:  00001000  |00000fff  |00000000  &ffffffff
13:  00002000  |00001fff  |00000000  &ffffffff
14:  00004000  |00003fff  |00000000  &ffffffff
15:  00008000  |00007fff  |00000000  &ffffffff
16:  00010000  |0000ffff  |00000000  &ffffffff
17:  00020000  |0001ffff  |00000000  &ffffffff
18:  00040000  |0003ffff  |00000000  &ffffffff
19:  00080000  |0007ffff  |00000000  &ffffffff
20:  00100000  |000fffff  |00000000  &ffffffff
21:  00200000  |001fffff  |00000000  &ffffffff
22:  00400000  |003fffff  |00000000  &ffffffff
23:  00800000  |007fffff  |00000000  &ffffffff
24:  01000000  |00ffffff  |00000000  &ffffffff
25:  02000000  |01ffffff  |00000000  &ffffffff
26:  04000000  |03ffffff  |00000000  &ffffffff
27:  08000000  |07ffffff  |00000000  &ffffffff
28:  10000000  |0fffffff  |00000000  &ffffffff
29:  20000000  |1fffffff  |00000000  &ffffffff
30:  40000000  |3fffffff  |00000000  &ffffffff
31:  80000000  |7fffffff  |00000000  &ffffffff
```
Pour n >= 32, tous les bits doivent être définis, et les "OU ffffffff" étape accomplit que, indépendamment de ce que l'étape précédente a pu faire. Le n <= 0 étape est alors un noop ainsi avec AND ffffffff.
```
  n:   1 << n    (1<<n)-1   n >= 32     n <= 0
---------------------------------------------
32:  00000001  |00000000  |ffffffff  &ffffffff
33:  00000002  |00000001  |ffffffff  &ffffffff
34:  00000004  |00000003  |ffffffff  &ffffffff
```
- Votre cas pour n >= 32 n'aide pas, car l'état de la case à cocher passage sera toujours fait, et si n >= sizeof(TheType) * CHAR_BIT, c'est UB, ce qui n'est pas affectée par le fait que vous essayez de papier au-dessus d'elle après le fait.
- Peut-être "objectifs" devrait aussi inclure des "lisible/compréhensible code" 🙂
- Ouais, c'est pourquoi j'ai indiqué les objectifs: pour indiquer qu'un code lisible était PAS le but. 🙂
- Ce qui est "UB" signifie? C'est ok si la première ligne est le produit d'une mauvaise valeur pour n>=32 parce que la ligne suivante corrige. J'ai ajouté un programme à la réponse qui prouve que l'algorithme. Honnêtement, ça a été tellement long que j'avais besoin de ce programme pour le prouver à moi-même.
- Comportement indéfini poisons de la totalité d'un programme dès que vous l'appelez. Vous ne pouvez pas "corriger" en les remplaçant par la suite. Et elle ne signifie absolument rien si vous constatez que le code passe pour produire des résultats corrects lors de l'essai, parce que l'UB signifie qu'il n'est pas obligatoire et peut se casser à tout moment (lorsqu'ils sont portés à une architecture différente, compilateur, de révision des normes, etc.). Le Code qui appelle UB est mauvaise et ne devrait pas être affiché sous forme de recommandation, et c'est la fin de celui-ci.
- Obtenir votre point, et je suis en désaccord. Exemple: x = uint32_t(1) << 40; x = 7; Même si la première affirmation est un comportement indéfini (pour certaines valeurs, par exemple, 40), la deuxième ligne est très bien défini le comportement et le résultat est ok. Sauf si "un comportement indéfini" comprend plantage d'une application, ou de corruption de la mémoire, il est bon.
- Pour être juste, j'ai été surpris de voir que << ne veut pas dire maj pour mon compilateur. Il signifie clairement le décalage avec la rotation qui je n'aurais pas cru (comportement indéfini).
- Il n'y a rien à en désaccord. La lettre de la Norme, c'est qu'une fois UB se produit, le comportement de l'ensemble du programme n'est pas défini. Ce n'est pas grave si vous faites quelque chose qui remplace complètement l'objet; l'UB a eu lieu, et il ne peut pas être annulée. Bien sûr, dans la pratique, probablement rien de mal n'arrive, que les compilateurs ne font pas leur mission est de ruiner votre vie. Mais il est formellement mal formé code, il est donc irresponsable de la dépeindre comme étant fine.
- Je suis d'accord avec vous sur le principe. Dans ce cas, je suis ok avec ce code, parce que je pense que "un comportement indéfini" signifie probablement "pas défini, mais sain d'esprit". En d'autres termes, aucun compilateur écrivain va garantir que la valeur retournée est ce que vous attendiez, mais ils ne seront probablement garantie de ne pas modifier quoi que ce soit d'autre que cette valeur ne produisant pas d'effets secondaires. Je vais ajouter un commentaire avec votre avertissement.
InformationsquelleAutor Harvey
1
```
((((1 << (n - 1)) - 1) << 1) | 1)
```
Dernier n bits. n doit être > 0. Travailler avec n = 32.

InformationsquelleAutor Enyby

-1

La fonction avec un test simple:

#include <stdio.h>
#include <stdint.h>
void setbits(uint32_t *x, int n)
{
*x |= 0xFFFFFFFF >> (32 - n);
}
int main()
{
for (int n = 1; n <= 32; ++n)
{
uint32_t x = 0;
setbits(&x, n);
printf("%2d: 0x%08X\n", n, x);
}
getchar();
return 0;
}

n doit être dans [1;32]
Cette solution fonctionne pour n'importe quel uint32_t variable définit son n bits de poids faible.
Ce n'est pas la couverture n==0.
Ce qui est vrai.

InformationsquelleAutor kol

Vous devez vous connecter pour publier un commentaire.