2
votes

Comment déterminer si un Int est de 16 bits

Je travaille avec des opérateurs binaires et logiques en C. Je connais le concept et le but de ces opérateurs, mais j'ai rencontré un petit problème.

Je dois déterminer si un entier x peut tenir dans un court. Je suis limité à l'utilisation des opérateurs ! ~ & ^ | + << >> . De plus, je ne peux utiliser que 8 de ces opérateurs.

Je connais plusieurs autres messages (comme celui-ci: Comment savoir si un int 32 bits peut tenir dans un 16 bits court ) qu'une solution comme

! (((((x) & 0xffff8000) >> 15) + 1) & 0x1fffe)

fonctionnerait très bien (merci à Emil Romanus). Cependant, je suis également interdit d'utiliser des constantes qui ne sont pas 0x0 et 0xff .

Je suis surtout confus sur la logique ici. Des idées?

EDIT: j'ai oublié de mentionner que les instructions conditionnelles sont également interdites. Donc pas de ifs, elses, boucles etc.

c binary architecture bit-manipulation

3 commentaires

! 0x0 == 1 ... ! 0x0 +! 0x0 == 2 ... juste en disant :)

@pmg ahhhh j'attrape ta dérive

Tout d'abord, connaissez-vous la taille de int et la taille de short pour votre architecture / compilateur? En supposant que sizeof (int) == sizeof (int32_t) , et sizeof (short) == sizeof (int16_t) est une grande hypothèse.

3 Réponses :

2
votes

c'est votre sollution

!((unsigned)~0 ^ (((0xff << (!!0xff << !!0xff << !!0xff << !!0xff))) | 0xff)))

ou sans ==

 !((unsigned)~0 - 0xffff)

 !((unsigned)~0 ^ 0xffff)

ou si seulement 0xff est autorisé

 (unsigned)~0 == 0xffff

4 commentaires

Je vois en quelque sorte ce que vous faites, mais pourquoi ajouter deux opérateurs ! à côté de chaque 0xff ? Cela n'annulerait-il pas simplement la négation? De plus, je suis censé n'utiliser que 8 opérateurs au maximum.

J'ai besoin du numéro 1 . !! convertit tout non zéro en 1

puis 3e sollution. Il n'y a pas d'autre moyen

@P__J__ tiens ma bière ;-)

1
votes

Pour la lisibilité définie invuint = ~ 0u et invushort = ~ ((short) 0u) , nous pouvons faire invuint - invushort qui est soit 0 ou non. 0 dans la norme C est égal à false , vous pouvez donc voir avec un simple ! (invuint - invushort) si un int unsigned s'inscrit dans un short non signé .

Mais ce n'est probablement pas ce qu'on vous demande de faire, ce serait un peu trop facile. Si vous avez besoin de savoir si le contenu d'un unsigned int s'inscrit dans un unsigned short , cela devient un peu plus compliqué.

Nous pouvons réutiliser ici incushort = ~ ((short) 0u) comme masque.

Avec an_uint = 0; an_uint = incushort nous définissons les bits les plus bas de an_uint à uns, donc nous avons 0x0000ffff . Inverser cela avec ~ an_uint vous permet d'obtenir 0xXXXX0000 où le X représente un nombre inconnu de uns. Donc, si sizeof (unsigned int) == sizeof (unsigned short) nous obtenons un 0 mais nous aurions pu obtenir cela plus simple, voir ci-dessus.

Si nous utilisons mask = 0xXXXX0000 comme masque pour obtenir tous les bits qui sont plus grands qu'un unsigned short avec uint_with_unknown_content & mask nous obtenons un 0 si uint_with_unknown_content s'inscrit dans un short non signé .

0 commentaires

1
votes

La solution est basée sur le fait que x ^ (x aura ses 16 MSB à zéro si les 17 MSB de x sont tous égaux et x peut être codé sur 16 bits.

Par conséquent,

int canNOTbemappedto16bits(int x) {
   int one = !0x0;  // 1 op
   int ffff = (unsigned short) ~0x0;//1 op
   int ffff0000 = (unsigned int) ~0x0 ^ ffff; // 2ops
   return   (x^(x<<one))&ffff0000 ; // 3ops
}

résout le problème.

Pour la lisibilité, les opérations sont fractionnées dans plusieurs instructions et pour réduire le nombre d'opérateurs utilisés le test final est inversé (cela ne semble pas interdit).

return (x^(x<<1))&(0xffff0000)==0;

7 opérations!

4 commentaires

J'aime votre logique et votre réponse est très claire et concise, mais comment procéder sans utiliser l'opérateur - ? De plus, je ne suis autorisé à utiliser que 8 opérateurs.

J'ai raté le fait que "-" était interdit. Mais la seule opération requise est "-1" et elle peut être remplacée par + (~ 0). Concernant le nombre d'opérateurs, il s'adapte, mais pas avec un oneliner. Je mets à jour la réponse.

@vastImmortalSuns Il y avait un bug dans la réponse précédente, mais j'ai trouvé un moyen beaucoup plus simple qui respecte pleinement les contraintes.

Ah, je vois! Merci d'avoir clarifié cela, je ne savais pas que vous pouviez même annuler 0, mais maintenant c'est parfaitement logique :)