Divisão e módulo em inteiros sem sinal com 6 registros

Dec 02 2020

Tenho que encontrar o algoritmo de tempo de registro (para uma máquina virtual) usando no máximo 6 registros (a, b, c, d, e, f) para dividir dois inteiros sem sinal N1 e N2 ([ambos são> = 0] positivo ou 0) onde se o divisor for 0, o resultado será 0 e a operação do módulo.

  • div -> N1 / N2
  • mod -> N1% N2

com comandos como

  • RESET a -> a = 0
  • ADICIONE ab -> a = a + b
  • SUB ab -> a = max (0, ab)
  • SHR a -> a = piso (a / 2)
  • SHL a -> a = floor (a * 2)
  • INC a -> a + = 1
  • DEC a -> a = max (0, a-1)
  • JUMP j -> pular para a linha j-th
  • JZERO xj -> se x for 0, então pule para k + j
  • JODD xj -> se x for ímpar, então pule para k + j

Existem algoritmos que podem me ajudar?

Só posso verificar se o valor em reg é ODD ou ZERO.

Obrigado pela ajuda.

Respostas

1 PeterCordes Dec 02 2020 at 18:34

Saturar-subtrair e jzeropermite comparar para menor ou igual (ou maior que), para que você possa implementar a versão C da resposta de njuffa em Como posso multiplicar e dividir usando apenas deslocamento e adição de bits? que produz quociente e resto. Como você tem adição não saturante, pode implementar a adição de embalagem (e, em seguida, fazer a detecção de execução manual verificando o envoltório, como Nathan faz em C.)

joddpermite que você teste o bit baixo, como if (x&1), o que permitiria a você implementar o algoritmo de multiplicação padrão também. Portanto, se você tiver um algoritmo de divisão que forneça apenas um quociente, poderá fazer remainder = dividend - quotient*divisorcom uma multiplicação log-tempo.


Perguntas e respostas sobre outras divisões binárias:

  • Como posso multiplicar e dividir usando apenas deslocamento e adição de bits? -outra resposta no mesmo Q&A, desta vez usando mudanças para "alinhar" o bit mais significativo do divisor com o dividendo antes de prosseguir com a divisão longa do livro escolar. Mas não está claro se é seguro sem inteiros de largura estendida.
  • Divisão de inteiro logarítmico de tempo usando apenas adição e subtração de deslocamento de bits
  • Como posso usar o deslocamento de bits para substituir a divisão inteira?
  • Dividir por 10 usando deslocamentos de bits? faz uma multiplicação em cada etapa, o que só é bom se você tiver uma multiplicação rápida ou para constantes conhecidas com poucos bits definidos, de forma que leve apenas alguns deslocamentos / soma. Outra vantagem é não exigir uma mudança para a direita, mas você tem uma mudança para a direita. (Ao contrário de alguns ISAs de brinquedo)