Divisão e módulo em inteiros sem sinal com 6 registros
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
Saturar-subtrair e jzero
permite 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.)
jodd
permite 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*divisor
com 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)