Como calcular um complemento usando operadores bit a bit de Ruby?

Question

O que eu quero:

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

o tamanho da entrada não está fixo como em 4 bits ou 8 bits. sim o seu um fluxo binário.

O que eu vejo:

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

Há uma ~ operador bit flipping

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

Eu acho que tem algo a ver com um pouco sendo usada para armazenar o sinal ou algo assim ... alguém pode explicar esta saída? Como faço para obter um complemento de um sem recorrer a manipulações de string como cortar os últimos n caracteres a partir da saída sprintf para obter "0110" ou substituindo 0 por 1 e vice-versa

Answer 1

Parece que você só quer virar quatro bits (o comprimento de sua entrada) -. Então você provavelmente vai querer XOR com 1111

Answer 2

Rubi apenas armazena um número (assinado). A representação interna deste número não é relevante: pode ser uma fixnum, bignum ou outra coisa. Portanto, o número de bits em um número também é indefinido: é apenas um número depois de tudo. Isto é contrário a, por exemplo C, onde um int provavelmente será 32 bits (fixo).

Então, o que faz o operador ~ faz então? Wel, apenas algo como:

class Numeric
    def ~
        return -self - 1
    end
end

... já que é o '~' representa quando se olha para os números do complemento de 2.

Então, o que está faltando em sua declaração de entrada é o número de bits que você quer mudar:. Um 32-bits ~ é diferente de um genérico ~ como é em Ruby

Agora, se você quer apenas para n-bit bits-flip você pode fazer algo como:

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

... mas você tem que especificar o número de bits a Flip. E isso não vai afetar a bandeira sinal, uma vez que um está fora de seu alcance com XOR:)

Answer 3

Consulte este pergunta por que.

Um problema com o seu método é que sua resposta esperada só é verdade se você só virar os quatro bits significativos:. 1001 -> 0110

Mas o número é armazenado com zeros à esquerda, e o operador ~ inverte todos os bits líderes também: 00001001 -> 11110110. Em seguida, o líder 1 é interpretado como o sinal negativo.

Você realmente precisa especificar o que a função é suposto fazer com números como 0b101 e 0b11011 antes que você possa decidir como implementá-lo. Se você só quer virar 4 bits que você pode fazer v^0b1111, como sugerido em outra resposta. Mas se você deseja inverter todos os bits importantes, ele fica mais complicado.

Editar

Aqui está uma maneira de inverter todos os bits significativos:

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

Isto dá

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

Esta não dá a sua saída desejada para ones_compliment (1), porque trata 1 como "1" não "01". Eu não sei como a função poderia inferir quantos zeros à esquerda que você quer, sem ter a largura como um argumento.

Answer 4

O que você está fazendo (usando o ~) operador, é de fato complemento de um um. Você está recebendo os valores que você não está esperando por causa da maneira como o número é interpretado por Ruby.

O que você realmente precisa fazer vai depender do que você está usando isso para. Ou seja, por que você precisa de um complemento de 1?

Answer 5

Se você está trabalhando com cordas que você poderia fazer:

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

Se você está trabalhando com números, você terá que definir o número de bits significativos porque:
0110 = 6; 1001 = 9;
110 = 6; 001 = 1;

Mesmo, ignorando o sinal, você provavelmente vai ter de lidar com isso.

Answer 6

Lembre-se que você está recebendo o complemento de um agora com ~ se você passar em um Fixnum: o número de bits que representam o número é uma quantidade fixa no interpretador e, portanto, existem levando 0 do em frente à representação binária de o número 9 (binário 1001). Você pode encontrar este número de bits por examinar o tamanho de qualquer Fixnum. (A resposta é retornado em bytes)

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

~ também é definido ao longo Bignum. Neste caso, se comporta como se todos os bits que são especificados no Bignum foram invertida, e em seguida, se houvesse uma cadeia infinita de 1s na frente daquele Bignum. Você pode, concebivelmente empurrar seu bitstream em um Bignum e inverter a coisa toda. No entanto, você precisa saber o tamanho do bitstream antes da inversão para obter um resultado útil para fora depois de ser invertida.

Para responder à pergunta como você colocá-la logo de cara, você pode encontrar a maior potência de 2 menor do que a sua entrada, dobrá-lo, subtrair 1, então XOR o resultado de que, com a sua entrada e sempre obter um complemento queridos de apenas os bits significativos em seu número de entrada.

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