Effectuer des opérations arithmétiques en binary en utilisant uniquement des opérateurs au niveau du bit

Dupliquer possible:
Comment puis-je multiplier et diviser en n’utilisant que le transfert et l’ajout de bits?

Je dois écrire des fonctions pour effectuer des soustractions, multiplications et divisions binarys sans utiliser d’opérateurs arithmétiques, à l’exception du contrôle de boucle. Je n’ai écrit que du code en Java auparavant, alors j’ai du mal à comprendre cela.

À partir de la soustraction, je dois écrire une fonction avec prototype

int bsub(int x, int y) 

Je sais que je dois convertir y en complément à deux pour le rendre négatif et l’append à x, mais je sais seulement comment faire cela en utilisant son opérateur complémentaire ~ et en ajoutant 1, mais je ne peux pas utiliser l’opérateur +.

La fonction badd a été fournie, et je pourrai l’implémenter en bsub si je peux comprendre comment créer un nombre négatif. Le code pour badd est présenté ci-dessous. Merci d’avance pour des conseils.

 int badd(int x,int y){ int i; char sum; char car_in=0; char car_out; char a,b; unsigned int mask=0x00000001; int result=0; for(i=0;i<32;i++){ a=(x&mask)!=0; b=(y&mask)!=0; car_out=car_in & (a|b) |a&b; sum=a^b^car_in; if(sum) { result|=mask; } if(i!=31) { car_in=car_out; } else { if(car_in!=car_out) { printf("Overflow occurred\n"); } } mask<<=1; } return result; } 

Bien, soustraire dans les opérations au niveau des bits sans les opérateurs + ou - est légèrement délicat, mais peut être fait. Vous avez l’idée de base avec le complément, mais sans utiliser + cela devient un peu délicat.

Vous pouvez le faire en configurant d’abord l’addition en bits, puis en utilisant la soustraction. Ce qui est utilisé pour le complément, donc le code ressemble à ceci:

 int badd(int n1, int n2){ int carry, sum; carry = (n1 & n2) << 1; // Find bits that are used for carry sum = n1 ^ n2; // Add each bit, discard carry. if (sum & carry) // If bits match, add current sum and carry. return badd(sum, carry); else return sum ^ carry; // Return the sum. } int bsub(int n1, int n2){ // Add two's complement and return. return badd(n1, badd(~n2, 1)); } 

Et puis, si nous utilisons le code ci-dessus dans un exemple:

 int main(){ printf("%d\n", bsub(53, 17)); return 0; } 

Ce qui finit par revenir 36 . Et c’est ainsi que la soustraction fonctionne avec des opérations uniquement au niveau du bit.

Après, la multiplication et la division deviennent plus compliquées, mais peuvent être faites; pour ces deux opérations, utilisez des quarts de travail avec addition et / ou soustraction pour faire le travail. Vous voudrez peut-être aussi lire cette question et cet article pour savoir comment le faire.

Vous devez d’abord implémenter l’addition binary:

Exemple avec 4 bits:

a = 1101 b = 1011

le masque ira de 0001 à 1000

 for (i=0;i<4;i++) { x = a & pow(2, i); //mask, you can shift left as well y = b & pow(2, i); z = x ^ y; //XOR to calculate addition z = z ^ carry; //add previous carry carry = x & y | x ^ carry | y ^ carry; //new carry } 

C'est un pseudocode. Le masque permet d'opérer petit à petit de gauche à droite. Vous devrez stocker z facilement dans une autre variable.

Une fois que vous avez l'addition, vous pourrez implémenter la soustraction en complétant et en ajoutant 1.

La multiplication va dans le même sens, mais un peu plus difficile. En gros, il s’agit de la même méthode de division que celle que vous avez apprise à l’école: utiliser des masques pour sélectionner les bits de manière pratique et append les résultats intermédiaires à l’aide de l’addition ci-dessus.

La division est un peu plus compliquée, cela prendrait un peu plus de temps à expliquer mais au fond c'est le même principe.