Rarement, mais toujours, les tâches des entretiens et des formations ont une valeur pratique. Il me fallait donc implémenter en Java une alternative aux opérations arithmétiques sur des valeurs entières. Heureusement, les premières pages des moteurs de recherche regorgent de solutions toutes faites pour les analogues bit à bit, et vous n'avez pas eu à vous casser la tête sur la plupart d'entre elles.
Franchement, j'ai été quelque peu surpris du manque de matériel sur Habré (ai-je mal regardé?), Et j'ai donc décidé de combler cette lacune, avec mes commentaires et ajouts.
Veuillez noter que dans les exemples avec des opérations au niveau du bit, les valeurs sont tronquées en un quartet: il n'y aura pas de différence fondamentale, mais plus facile à comprendre.
Une addition
Algorithme:
private int add(int summand, int addend)
{
/*.*/
int carry = 0x00;
/* , .*/
while(addend != 0x00)
{
/* .*/
carry = (summand & addend);
/* , .*/
summand = summand ^ addend;
/* .*/
addend = (carry << 1);
}
return summand;
}
Vous devez d'abord vous souvenir du transfert dans la catégorie senior. Dans le système décimal, sa définition (pour le chiffre courant) comprend des valeurs comprises entre 10 et 18:
109 +
019 =
128
Dans le système binaire, tout ce qui est supérieur à un est transféré:
0001 +
0001 =
----
0010
ou comme ça:
0011 +
0011 =
----
0110
Dans le dernier exemple, les bits les moins significatifs sont ajoutés en premier:
1 + 1 = 10 ()
Zéro reste dans le bit courant, et on passe au plus significatif, où il participe en plus:
1 + 1 + 1 = 11 ()
le plus bas reste dans l'actuel, le plus ancien va plus loin. À partir de là, vous pouvez déduire la règle selon laquelle dans le système binaire pour un bit courant, les valeurs de deux à trois inclusivement tombent sous le report.
Dans la partie concernant l'algorithme, il convient de prêter attention à l'instruction de détermination de la présence / absence de transfert en utilisant l'exemple des valeurs précédentes:
carry = (summand & addend);
0011 = 0011 & 0011
Il ne s'agit pas encore d'un transfert, mais de la mise en place de "drapeaux" sur les chiffres, dont l'addition laisse le transfert, c'est-à-dire add carry est lorsque les bits sont identiques.
Dès que quelque chose s'est déjà éclairci, maintenant le premier terme doit être libéré des bits pour lesquels le transfert est pris en compte:
summand = summand ^ addend;
0000 = 0011 ^ 0011
Comme vous le savez, l'opérateur XOR au niveau du bit ne définira les bits que si les valeurs de bits sont opposées.
La troisième étape de la boucle consiste à convertir directement les indicateurs de retenue en une retenue. Pour ce faire, ils sont décalés d'un cran vers la gauche et affectés au deuxième terme:
addend = (carry << 1);
0110 = (0011 << 1);
À la prochaine itération, le transfert ne sera pas corrigé, car:
carry = (summand & addend);
0000 = 0000 & 0110
La deuxième étape nous donnera:
summand = summand ^ addend;
0110 = 0000 ^ 0110,
Quelle est la somme souhaitée, et la troisième étape mettra fin à la boucle while ():
addend = (carry << 1);
0000 = (0000 << 1)
Soustraction
Algorithme:
private int sub(int minuend, int subtrahend)
{
/* .*/
int borrow = 0x00;
/* , .*/
while(subtrahend != 0x00)
{
/* .*/
borrow = ((~minuend) & subtrahend);
/* , .*/
minuend = minuend ^ subtrahend;
/* .*/
subtrahend = (borrow << 1);
}
return minuend;
}
Equivalent au précédent, à la seule différence que l'emprunt de bits aux bits les plus significatifs est implémenté par inversion d' implication inverse . Eh bien, nous renommons les variables locales.
Multiplication
Algorithme:
public int multiply(int mul1, int mul2)
{
int result = 0;
/* .*/
while(mul2 != 0)
{
/* ...*/
if ((mul2 & 1) == 1)
{
/* .*/
result = add(result, mul1);
}
/* ("")*/
mul1 <<= 1;
/* if()*/
mul2 >>>= 1;
}
return result;
}
Retour aux sources: multiplication longue en système décimal:
25 *
05 =
--
125 +
00
---
125
ceux. nous multiplions chaque chiffre du deuxième facteur par le premier facteur. De là, il s'ensuit que le produit du bit le plus significatif est décalé d'un pas vers la gauche. Enfin, ajoutez les valeurs intermédiaires. La même chose se produit au niveau du bit:
0110 *
0011 =
----
0110 +
0 110 +
00 00 +
000 0 +
- ----
1 0010
Nous concluons que l'algorithme n'a qu'à ajouter le premier facteur à lui-même chaque fois qu'un bit défini est rencontré dans le second facteur, naturellement, en tenant compte de la règle de transfert vers le bit le plus significatif:
if ((mul2 & 1) == 1) //(0011 & 0001) == 0001
{
result = add(result, mul1); //0110 = 0000 + 0110
}
Ensuite, le premier multiplicateur est décalé d'un bit vers la gauche (on forme une "échelle"):
mul1 <<= 1; //1100 = 0110 << 1;
Maintenant, nous déterminons s'il y a un peu dans le deuxième bit le plus important du deuxième facteur:
mul2 >>>= 1; //0001 = 0011 >>> 1;
Le cycle se poursuit jusqu'à ce que le deuxième facteur soit zéro. Je voudrais attirer votre attention sur ce qui suit: une instance de cet algorithme marche de ressource en ressource, où le décalage logique du deuxième facteur (mul2 >>> = 1) est remplacé par un décalage arithmétique (mul2 >> = 1) . Il provient probablement de l'implémentation en C / C ++, où il y a le mot - clé unsigned et cette substitution n'est pas un problème. Cependant, en Java, tous les types de nombres sont signés, et si le deuxième facteur est représenté par une valeur négative, un tel oubli conduira l'algorithme à tomber dans une boucle infinie, car le deuxième facteur remplira toujours sa condition:
1000 >>1; //
1100 >>1; // ( 0100)
1110 >>1; // 0010
1111 >>1; // -1
Division
Algorithme:
private int divide(int dividend, int divisor)
{
/*, .*/
int quotient = 0x00, mask = 0x01;
/* .*/
int temp = divisor;
/* .*/
int sign = ((dividend < 0)^(divisor < 0)) ? sign = -1 : 1;
/* .*/
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
/* 0 .*/
if (dividend < divisor) return quotient;
while(dividend > 0 || divisor != 0)
{
/* .*/
if ((dividend >= (divisor << 0x01)) && ((divisor << 0x01) > 0))
{
divisor <<= 0x01;
mask <<= 0x01;
}
/* .*/
else
{
/* "" .*/
quotient = quotient | mask;
/* .*/
dividend = sub(dividend, divisor);
/* .*/
divisor = temp;
mask = 0x01;
}
}
return multiply(quotient, sign);
}
La division n'a pas fonctionné aussi bien qu'avec les exemples précédents: je devais écrire un vélo (pas frapper fort).
La division est la soustraction du diviseur du dividende tant que le quotient est supérieur ou égal à zéro. Avec cette approche, il suffit de définir un compteur dont la valeur est incrémentée après chaque opération de soustraction. Sa valeur finale est le particulier:
count = 0;
1) 7 - 3 = 4; count = 1;
2) 4 - 3 = 1; count = 2;
7 / 3 = count;
L'inconvénient de cette approche devient particulièrement perceptible lors de la fourniture d'un dispositif avec des ressources limitées de séquence d'instructions, telles que: 2147483647/1; 2147483647/2; 2147483647/3 , il semble que l'application soit gelée.
Travailler au niveau du bit serait beaucoup plus efficace. Mais la seule solution trouvée présente l'inconvénient que pour une inférence correcte, le type de variables est requis, un cran au-dessus de la plage couverte, c'est-à-dire si l'entrée est courte , le type de variables locales doit être int , sinon le résultat de la division de grandes valeurs sera surprenant. Dans mon cas, la situation a été aggravée par l'absence du type long.
Mais revenons à nos béliers.
Pour comprendre le fonctionnement de l'algorithme, vous devez vous souvenir de l'ordre de division des colonnes:
= 6, = 2;
0110|0010
----
110|10 //
, , :
1) (1 >= 10) -> ,
110|10
--
0
2) (11 >= 10) -> ,
110|10
-10 --
-- 01
01
Ici plus en détail. A l'échappement, nous avons obtenu ce qui suit: nous avons "poussé" le diviseur vers la gauche jusqu'à la décharge où il minimisait la différence avec le divisible:
2.1) 0110 / 0010 -> 0110 - 0100 = 0010 = 2.
3) (10 >= 10) -> ,
110|10
-10 --
-- 011
010
-10
--
00
Ce mécanisme est implémenté dans l'algorithme. Dans une boucle while (), le diviseur doit être déplacé vers la gauche jusqu'à ce qu'il satisfasse la règle ci-dessus. En parallèle, le masque privé est décalé. L'opérateur de branchement if () dit: "Vous pouvez décaler si seul le résultat de cette opération ne viole pas la règle de base." Un contrôle supplémentaire pour un nombre négatif est dû au fait qu'en Java, l'ensemble de bits le plus significatif est un nombre négatif. Sans cela, le cycle tombera à l'infini:
//((divisor << 0x01) > 0) ,
1) 0111 >= 0010<<1
2) 0111 >= 0100<<1
3) 0111 >= 1000<<1 //! - if() , , .
4) 0111 >= 0000<<1
....
Dès que l'algorithme cesse de répondre aux conditions if (), le code entre dans le else, où le bit de masque est défini sur le quotient:
quotient = quotient | mask;
0010 = 0000 | 0010
Cela revient à définir les bits pour une division longue. Ensuite, le diviseur est soustrait du dividende:
dividend = sub(dividend, divisor);
0010 = 0110 - 0100
Après cela, le diviseur et le masque reviennent à leur état d'origine et le cycle recommence:
divisor = temp;
mask = 0x01;
Enfin, je voudrais ajouter quelques mots sur le code supplémentaire.
L'algorithme ci-dessus suppose la division uniquement des nombres positifs obtenus par le code complémentaire:
dividend = dividend < 0 ? add((~dividend), 1) : dividend;
divisor = divisor < 0 ? add((~divisor), 1) : divisor;
Ici, ce qui suit se produit: si le nombre est négatif, alors ses bits sont inversés, et le résultat est ajouté avec un et nous obtenons une valeur positive (absolue). La même règle s'applique aux nombres positifs, par exemple:
6 = 0110 -> ~6 = 1001 = 1001 + 1 = 1010 = -6
-6 = 1010 -> ~-6 = 0101 = 0101 + 1 = 0110 = 6
Mais il y a une exception - c'est le plus grand nombre négatif d'un type donné, par exemple:
int -2147483648 ->
~1000 0000 0000 0000 0000 0000 0000 0000 =
0111 1111 1111 1111 1111 1111 1111 1111 + 1 =
1000 0000 0000 0000 0000 0000 0000 0000.
Faites attention.