O（logn）のランタイムで2進数のアルゴリズムを除算

Question

O（logn）でリマインダなしで16ビットの2進数の除算を計算するプログラムをアセンブリ言語で書く必要があります。私はそれを行うための効率的なアルゴリズムがあるのか​​疑問に思いました。

ウェブ上のいくつかのアルゴリズムを発見し、それらのすべての数が特定のビットへのアクセスを探している、と私は..それを行うことができない場合

私がある持っている唯一の算術演算

+、 - 、左右にシフトするが、それぞれの操作は1つだけである、&、|、！そして...どうやらこのすべてが動作するはず

おかげで、

Eliav

Answer 1

のthats。 それはあなたを助けますか？

C-スタイル：

c=1; 
// find the maximum n for b*2^n <= a 
// c=2^n 
while((b << 1) <= a) { 
    b = b << 1; 
    c = c << 1; 
} 
while (c > 0) { 
    if (a - b >= 0) { 
     a -= b; 
     result += c; 
    } 
    c = c >> 1; 
    b = b >> 1; 
} 

組立スタイル：

registers s0,s1,s2,s3, zero 
syntax <instr.> <dest>,<src>,<arg> 

%result: s0 
%a: s1 
%b: s2 
%c: s3 

add, s3, zero, 1 



loop_1_start: 
left_shift s4,s2,1 
jump_if_greater s4,s1,loop_1_end 

left_shift s2,s2,1 
left_shift s3,s3,1 

jump loop_1_start 
loop_1_end: 

loop_2_start: 
jump_if_greate_or_equal s3,zero,loop_2_end 

if_start: 
sub s4,s1,s2 
jump_if_smaller s4, zero, if_end 
sub s1,s1,s2 
add s0,s0,s3 
if_end: 


right_shift s2,s2,1 
right_shift s3,s3,1 

jump loop_2_start 
loop_2_end: