Comment puis-je utiliser des opérateurs binaires pour voir quel est le plus grand de deux entiers non signés, sans utiliser d'opérateurs arithmétiques ou d'opérateurs de comparaison?
3 Réponses :
Si vous avez affaire à la représentation décimale des nombres, vous diriez que celle avec le plus de chiffres est la plus grande.
Que faire si deux nombres ont le même nombre de chiffres? Eh bien, vous comparez chaque chiffre tour à tour, en commençant par le plus significatif.
En décimal, ce serait difficile tout en répondant à vos exigences. Mais en binaire, nous pouvons effectuer des tests de vérité simples. En tant que telle, cette approche peut être utilisée ici.
+---+---+---+---+ +---+---+---+---+ | 0 | 1 | 1 | 0 | 6 | 0 | 1 | 1 | 0 | 6 +---+---+---+---+ +---+---+---+---+ → ↑ ↑ → → ↑ ↑ +---+---+---+---+ +---+---+---+---+ | 0 | 0 | 1 | 0 | 2 | 0 | 1 | 0 | 0 | 4 +---+---+---+---+ +---+---+---+---+
En tant que tel, cela fonctionne pour les entiers non signés de même taille:
Il existe une solution encore plus simple qui consiste à trouver l'exclusif ou des deux nombres d'entrée.
Salut, merci pour la réponse. Lorsque vous dites isoler le plus significatif, vous voulez dire en utilisant l'opérateur de décalage. À ce droit c'est.
Considérons deux entiers 4 (0100) et 3 (0011). Nous devons générer la plus grande série de sous-bits qui différencie les deux entiers, par exemple au-dessus, il est 0100 (puisque le troisième bit est différent), alors nous pouvons simplement savoir lequel est le plus grand en faisant le bit AND:
#include <stdio.h>
int main()
{
int a, b;
printf("Enter two numbers\n");
scanf("%d%d", &a, &b);
int diff = a ^ b;
if (diff) //true means both are not equal
{
diff = diff | (diff >> 1);
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff ^= diff >> 1;
int res = (a & diff) ? 1 : 0;
if (res)
printf("%d greater than %d", a, b);
else
printf("%d greater than %d", b, a);
}
else //both equal
{
printf("Both are equal\n");
return 0;
}
return 0;
}
Le code est comme suit:
0100 & 0100 = 0100 > 0 0011 & 0100 = 0
J'ai vérifié dans mon système, cela a fonctionné (Ubuntu).
Merci pour l'aide. Je ferai le calcul plus tard quand je rentrerai du travail aujourd'hui. Au moins, j'aurai une sorte de guide. Ceci est vraiment utile.
@ Ryanv048 Vous êtes les bienvenus. Veuillez voter pour la réponse et accepter, si cela est utile.
J'étais curieux de savoir si vous utilisiez un int signé . Donc, j'ai ajouté une fonction de test dérivée de votre algorithme à mon programme de test [et une qui utilise unsigned]. Votre code d'origine échoue pour les valeurs qui diffèrent dans le bit de signe. Lorsque vous passez à non signé, cela fonctionne correctement. Ainsi, vous souhaiterez peut-être modifier votre code pour utiliser un unsigned int .
@CraigEstey Oui, vous avez raison. Le code ne fonctionne pas pour les nombres avec un signe différent. Mais la question ---> "plus grand de deux entiers non signés"
L'utilisation de XOR (OU exclusif) et SHL (décalage vers la gauche) dans une boucle fera l'affaire.
XOR (en C: ^ ) est la manière normale [en bas niveau H / W] de tester l'égalité. C'est une porte logique de base.
Si le XOR de deux nombres est zéro, ils sont égaux.
Mais, le XOR de deux nombres produit un masque de bits où si l'un des bits de deux nombres est différent, le bit XOR correspondant est un 1 (0 sinon).
En décalant et en masquant le MSB, nous pouvons trouver le bit le plus à gauche qui est différent.
Voici un code qui illustre cela. Il dispose d'un test de diagnostic afin que vous puissiez vérifier votre fonction:
0.000000000 dotest: cmpxor 00000000/000000FF/00000001 (ELAPSED: 0.001531766) 0.001538215 dotest: cmpki 00000000/000000FF/00000001 (ELAPSED: 0.000467471) 0.002008009 dotest: cmpku 00000000/000000FF/00000001 (ELAPSED: 0.000475924) 0.002488059 dotest: cmpxor 01000000/FFFFFFFF/01000000 (ELAPSED: 0.000398438) 0.002888709 dotest: cmpki 01000000/FFFFFFFF/01000000 cmpki : FAIL a=80000000 b=01000000 cmps=1 cmpx=-1 cmpki : 1 errors (ELAPSED: 0.000237286) 0.003127983 dotest: cmpku 01000000/FFFFFFFF/01000000 (ELAPSED: 0.000467515) complete
MISE À JOUR:
J'ai amélioré la suite de tests de diagnostic. Et, j'ai ajouté une analyse comparative.
J'ai également ajouté deux fonctions dérivées de la réponse de Krishna.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef unsigned int u32;
typedef unsigned long long u64;
u32 opt_L = 0;
int opt_e; // number of errors to show per func
int opt_k; // don't stop next test if error
int opt_v; // show all values
// RETURNS -1=a<b, 0=a==b, +1=a>b
int
cmpxor(u32 a,u32 b)
{
u32 xor;
u32 msb;
int cmp = 0;
// get a mask for the most signifcant bit
msb = 1u << 31;
// which bits are different
xor = a ^ b;
while (xor != 0) {
// is the most significant bit different? if so, we are done
if (xor & msb) {
if (a & msb)
cmp = 1;
else
cmp = -1;
break;
}
xor <<= 1;
a <<= 1;
}
return cmp;
}
int
cmpstd(u32 a,u32 b)
{
int cmp = 0;
if (a < b)
cmp = -1;
if (a > b)
cmp = 1;
return cmp;
}
int
cmpki(int a, int b)
{
int diff = a ^ b;
int res;
do {
// Both are equal
if (diff == 0) {
res = 0;
break;
}
diff = diff | (diff >> 1);
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff ^= diff >> 1;
// Conditonal operator is not a relational operator
res = (a & diff) ? 1 : -1;
} while (0);
return res;
}
int
cmpku(u32 a, u32 b)
{
u32 diff = a ^ b;
int res;
do {
// Both are equal
if (diff == 0) {
res = 0;
break;
}
diff = diff | (diff >> 1);
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff ^= diff >> 1;
// Conditonal operator is not a relational operator
res = (a & diff) ? 1 : -1;
} while (0);
return res;
}
double tsczero;
double tscbeg;
double
tscget(void)
{
struct timespec ts;
double sec;
clock_gettime(CLOCK_MONOTONIC,&ts);
sec = ts.tv_nsec;
sec /= 1e9;
sec += ts.tv_sec;
if (tsczero == 0)
tsczero = sec;
sec -= tsczero;
return sec;
}
#define msgbeg(_fmt...) \
do { \
tscbeg = tscget(); \
printf("%13.9f ",tscbeg); \
printf(_fmt); \
fflush(stdout); \
} while (0)
void
msgend(void)
{
double tscend = tscget();
printf(" (ELAPSED: %.9f)\n",tscend - tscbeg);
}
typedef struct {
int (*tst_fnc)(u32,u32);
const char *tst_tag;
} tst_t;
tst_t tstlist[] = {
{ .tst_tag = "cmpxor", .tst_fnc = (void *) cmpxor },
{ .tst_tag = "cmpki", .tst_fnc = (void *) cmpki },
{ .tst_tag = "cmpku", .tst_fnc = (void *) cmpku },
{ .tst_tag = NULL }
};
int taglen;
int
dotest(tst_t *tst,u64 lo,u64 hi,u32 inc)
{
u64 a;
u64 b;
int cmpx;
int cmps;
int badflg;
int hangflg = 1;
int ecnt = 0;
msgbeg("dotest: %-*s %8.8llX/%8.8llX/%8.8X",taglen,tst->tst_tag,lo,hi,inc);
for (a = lo; a <= hi; a += inc) {
for (b = lo; b <= hi; b += inc) {
cmps = cmpstd(a,b);
cmpx = tst->tst_fnc(a,b);
badflg = (cmps != cmpx);
if (badflg || opt_v) {
if (hangflg) {
hangflg = 0;
printf("\n");
}
printf("%-*s: %s a=%8.8llX b=%8.8llX cmps=%d cmpx=%d\n",
taglen,tst->tst_tag,badflg ? "FAIL" : "PASS",a,b,cmps,cmpx);
if (badflg)
++ecnt;
if (opt_v)
continue;
if (ecnt >= opt_e)
break;
}
}
if (opt_v)
continue;
if (ecnt >= opt_e)
break;
}
if (ecnt || opt_v) {
if (hangflg)
printf("\n");
printf("%-*s: %d errors",taglen,tst->tst_tag,ecnt);
}
msgend();
if (ecnt)
ecnt = 1;
return ecnt;
}
typedef struct {
u32 rng_lo;
u32 rng_hi;
u32 rng_inc;
} rng_t;
rng_t rnglist[] = {
{ .rng_lo = 0x00000000, .rng_hi = 0x000000FF, .rng_inc = 1 },
{ .rng_lo = 0x01000000, .rng_hi = 0xFFFFFFFF, .rng_inc = 0x01000000 },
{ .rng_inc = 0 }
};
int
dorange(rng_t *rng)
{
tst_t *tst;
int code = 0;
for (tst = tstlist; tst->tst_tag != NULL; ++tst) {
code = dotest(tst,rng->rng_lo,rng->rng_hi,rng->rng_inc);
if (! opt_k) {
if (code)
break;
}
}
return code;
}
int
main(int argc,char **argv)
{
int code = 0;
--argc;
++argv;
for (; argc > 0; --argc, ++argv) {
char *cp = *argv;
if (*cp != '-')
break;
cp += 2;
switch (cp[-1]) {
case 'e':
opt_e = (*cp != 0) ? atoi(cp) : 0x7FFFFFFF;
break;
case 'k':
opt_k = ! opt_k;
break;
case 'L':
opt_L = (*cp != 0) ? atoll(cp) : 65536;
break;
case 'v':
opt_v = ! opt_v;
break;
}
}
setlinebuf(stdout);
if (opt_L == 0)
opt_L = 256;
if (opt_e == 0)
opt_e = 1;
if (opt_v)
opt_e = 0x7FFFFFFF;
// get max length of function name
for (tst_t *tst = tstlist; tst->tst_tag != NULL; ++tst) {
int curlen = strlen(tst->tst_tag);
if (curlen > taglen)
taglen = curlen;
}
// do all test ranges
for (rng_t *rng = rnglist; rng->rng_inc != 0; ++rng) {
code = dorange(rng);
if (code)
break;
}
if (code == 0)
printf("complete\n");
return code;
}
Voici la sortie du test:
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int u32;
// RETURNS -1=a<b, 0=a==b, +1=a>b
int
cmpxor(u32 a,u32 b)
{
u32 xor;
u32 msb;
int cmp = 0;
// get a mask for the most signifcant bit
msb = 1u << 31;
// which bits are different
xor = a ^ b;
while (xor != 0) {
// is the most significant bit different? if so, we are done
if (xor & msb) {
if (a & msb)
cmp = 1;
else
cmp = -1;
break;
}
xor <<= 1;
a <<= 1;
}
return cmp;
}
int
cmpstd(u32 a,u32 b)
{
int cmp = 0;
if (a < b)
cmp = -1;
if (a > b)
cmp = 1;
return cmp;
}
int
main(int argc,char **argv)
{
u32 a;
u32 b;
int cmpx;
int cmps;
u32 opt_L = 0;
int code = 0;
--argc;
++argv;
for (; argc > 0; --argc, ++argv) {
char *cp = *argv;
if (*cp != '-')
break;
cp += 2;
switch (cp[-1]) {
case 'L':
opt_L = (*cp != 0) ? atoll(cp) : 65536;
break;
}
}
if (opt_L == 0)
opt_L = 1024;
for (a = 0; a < opt_L; ++a) {
for (b = 0; b < opt_L; ++b) {
cmps = cmpstd(a,b);
cmpx = cmpxor(a,b);
if (cmps != cmpx) {
printf("a=%8.8X b=%8.8X cmps=%d cmpx=%d\n",
a,b,cmps,cmpx);
code = 1;
break;
}
}
if (code)
break;
}
if (code == 0)
printf("complete\n");
return code;
}
La raison pour laquelle j'ai amélioré la suite de tests était que je sentais que l'utilisation d'un int signé dans cmpki [l'algorithme original de Krishna] pouvait avoir des problèmes pour les nombres avec le bit de signe défini [à cause de la sémantique d'un décalage arithmétique à droite par rapport à un décalage logique à droite ]. Et, parce que le problème initial indiquait que les numéros n'étaient pas signés.
J'ai ajouté une version non signée et cela a résolu le problème.
@CraigEstey Vous ne devez pas utiliser d'opérateurs de comparaison. while (xor != 0) -> Comparaison
Merci Craig pour l'aide, mes excuses également pour la réponse tardive. Cela me donne un guide sur ce qu'il faut faire. J'apprécie vraiment cela.
Nous ne devons utiliser aucun opérateur de comparaison. Vous avez utilisé les opérateurs < , > , == et != .
@KrishnaKanthYenumula Je n'ai utilisé que xor != 0 [dans le while ]. L'utilisation de any if/while/?: Est une comparaison même si c'est if (val) - on ne peut pas contourner cela. Vous avez utilisé if (diff == 0) . Je n'ai pas utilisé < ou > . Si vous faites référence à cmpstd , c'est juste une partie de la suite de tests unitaires pour fournir une référence pour la validation du code "réel" (par exemple cmpxor [et cmpki/cmpku ]). Comme je l'ai mentionné, XOR est une porte logique de base qui est utilisée dans le matériel pour tester l'égalité / l'inégalité. Le problème est vraiment de savoir comment utiliser la logique de base. Le problème ne veut que gt , mais nous avons tous les deux cmp pour cmp
@CraigEstey Merci pour le pointage. Je l'ai édité. J'ai supprimé l'utilisation de l'opérateur == . In if(res) if(diff) ------> Les opérateurs de comparaison ne sont pas utilisés
entiers signés ou non signés? 64 bits, 32 bits, 16 bits ou 8 bits? Qu'avez-vous essayé?
désolé son non signé.
Astuce: en C, zéro est faux, non nul est vrai. C'est la seule façon d'obtenir une branche sans opérateur de comparaison.
Voir aussi geeksforgeeks.org/...
Pour comparer deux entiers non signés à l'aide d'opérations au niveau du bit, vous devez trouver le bit le plus significatif où les deux diffèrent dans leur représentation binaire. Shift et masque en boucle. Lent - mais c'est pourquoi les ordinateurs fournissent les opérations sous la forme d'un seul opcode et ne vous obligent pas à faire des exercices de devoirs comme celui-ci.
Conseils: (1) les bits qui ont la même valeur dans les deux entrées n'affectent pas la réponse. (2) Une opération exclusive ou (
^) vous indiquera quels bits diffèrent. (3) Parmi les bits où les entrées diffèrent, le plus significatif seul détermine quelle entrée (le cas échéant) est la plus grande.