Comment calculer son complément à l'aide des opérateurs au niveau des bits de Ruby?

Question

Ce que je veux:

assert_equal 6, ones_complement(9)   # 1001 => 0110
assert_equal 0, ones_complement(15)  # 1111 => 0000
assert_equal 2, ones_complement(1)   # 01 => 10

la taille de l'entrée n'est pas fixée comme dans 4 bits ou 8 bits. c'est plutôt un flux binaire.

Ce que je vois:

v = "1001".to_i(2)                 => 9

Il y a un opérateur qui tourne un peu ~

(~v).to_s(2)                       => "-1010"
sprintf("%b", ~v)                  => "..10110"
~v                                 => -10

Je pense que cela a quelque chose à voir avec un bit utilisé pour stocker le signe ou quelque chose ... Quelqu'un peut-il expliquer cette sortie? Comment obtenir un complément sans recourir à des manipulations de chaîne, telles que couper les n derniers caractères de la sortie du sprintf pour obtenir "0110"? ou en remplaçant 0 par 1 et vice versa

Answer 1

On dirait que vous voulez seulement retourner quatre bits (la longueur de votre entrée) - vous voulez donc probablement XOR avec 1111.

Answer 2

Ruby enregistre simplement un numéro (signé). La représentation interne de ce nombre n'est pas pertinente: il peut s'agir d'un FixNum, d'un BigNum ou de quelque chose d'autre. Par conséquent, le nombre de bits dans un nombre n'est pas non plus défini: il ne s'agit que d'un nombre. Ceci est contraire à l'exemple C, où un int sera probablement de 32 bits (fixe).

Alors, que fait l'opérateur ~? Wel, juste quelque chose comme:

class Numeric
    def ~
        return -self - 1
    end
end

... puisque c'est ce que '~' représente quand on regarde les nombres de complément à 2.

Donc, ce qui manque dans votre déclaration d'entrée, c'est le nombre de bits que vous voulez changer: un ~ 32 bits est différent d'un générique ~ comme en Ruby.

Maintenant, si vous voulez juste bips n-bits, vous pouvez faire quelque chose comme:

class Numeric
    def ones_complement(bits)
        self ^ ((1 << bits) - 1)
    end
end

... mais vous devez spécifier le nombre de bits à retourner. Et cela n’affectera pas le drapeau, puisque celui-ci est hors de portée avec XOR:)

Answer 3

Voir cette question pour savoir pourquoi.

Un problème avec votre méthode est que votre réponse attendue n’est vraie que si vous inversez les quatre bits significatifs: 1001 - > 0110 .

Mais le numéro est stocké avec des zéros à gauche et l'opérateur ~ inverse également tous les bits de gauche: 00001001 - > 11110110 . Ensuite, le 1 de départ est interprété comme le signe négatif.

Vous devez vraiment spécifier ce que la fonction est censée faire avec des nombres tels que 0b101 et 0b11011 avant de pouvoir décider de la mise en œuvre. Si vous ne voulez jamais retourner que 4 bits, vous pouvez faire v ^ 0b1111 , comme suggéré dans une autre réponse. Mais si vous voulez retourner tous les bits significatifs, cela devient plus compliqué.

modifier

Voici un moyen de retourner tous les bits significatifs:

def maskbits n
  b=1
  prev=n;
  mask=prev|(prev>>1)
  while (mask!=prev)
    prev=mask;
    mask|=(mask>>(b*=2))
  end
  mask
end

def ones_complement n
  n^maskbits(n)
end

Cela donne

p ones_complement(9).to_s(2)  #>>"110" 
p ones_complement(15).to_s(2) #>>"0"
p ones_complement(1).to_s(2)  #>>"0"

Ceci ne donne pas le résultat souhaité pour ones_compliment (1), car il traite 1 comme "" 1". pas "01". Je ne sais pas comment la fonction pourrait déduire le nombre de zéros que vous voulez sans prendre la largeur en argument.

Answer 4

Ce que vous faites (à l'aide de l'opérateur ~ ) est bien un complément à un. Vous obtenez ces valeurs auxquelles vous ne vous attendez pas à cause de la façon dont le nombre est interprété par Ruby.

Ce que vous devez réellement faire dépend de l'utilisation que vous en faites. C'est-à-dire, pourquoi avez-vous besoin d'un complément de 1?

Answer 5

Si vous travaillez avec des chaînes, vous pouvez le faire:

s = "0110"
s.gsub("\d") {|bit| bit=="1"?"0":"1"}

Si vous travaillez avec des nombres, vous devrez définir le nombre de bits significatifs pour les raisons suivantes:
0110 = 6; 1001 = 9;
110 = 6; 001 = 1;

Même en ignorant le signe, vous devrez probablement vous en occuper.

Answer 6

N'oubliez pas que vous obtenez actuellement le complément à one avec ~ si vous passez dans un Fixnum: le nombre de bits représentant ce nombre est une quantité fixe dans l'interpréteur et il existe donc des zéros en tête devant la représentation binaire de le nombre 9 (binaire 1001). Vous pouvez trouver ce nombre de bits en examinant la taille de tout Fixnum. (la réponse est renvoyée en octets)

1.size            #=> 4
2147483647.size   #=> 4

~ est également défini sur Bignum. Dans ce cas, il se comporte comme si tous les bits spécifiés dans le Bignum étaient inversés, puis s'il y avait une chaîne infinie de 1 devant ce Bignum. Vous pouvez éventuellement pousser votre train de bits dans un Bignum et inverser le tout. Cependant, vous aurez besoin de connaître la taille du train avant l’inversion pour obtenir un résultat utile après l’inversion.

Pour répondre à la question dès que vous la posez, vous pouvez trouver la plus grande puissance de 2 de moins que votre entrée, la doubler, soustraire 1, puis XOR le résultat avec votre entrée et obtenir toujours un complément complémentaire. uniquement les bits significatifs de votre numéro d'entrée.

def sig_ones_complement(num)
  significant_bits = num.to_s(2).length
  next_smallest_pow_2 = 2**(significant_bits-1)
  xor_mask = (2*next_smallest_pow_2)-1
  return num ^ xor_mask
end