forum.boolean.name - Деление 8bit на 8bit

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Деление 8bit на 8bit (http://forum.boolean.name/showthread.php?t=13104)

Деление 8bit на 8bit

Привет, в математике полный лох, поэтому спрошу здесь -
нужен алгоритм целочисленного деления одной восьмибитной переменной на другую восьмибитную, используя только SHR/SHL и вычитание/сложение.
Чтото типа такого:

PHP код:


		
			
Var

      a,b,b1,q,r : byte;

begin

      a := 100;

      b := 15;

      b1 := b;

      while b1 <= a do 

            begin

                  b1 := b1 shl 1;

            end;

      {b1 > a, b1 = b * (некоторая степень 2)}

      q:=0; 

      r:=a;

      {инвариант: q, r - частное и остаток при делении a на b1,

      b1 = b * (некоторая степень 2)}

      while b1 <> b do

            begin

                  b1 := b1 shr 1 ; q := q shl 1;

                  { a = b1 * q + r, 0 <= r, r < 2 * b1}

                  if r >= b1 then 

                        begin

                              r := r - b1;

                              q := q + 1;

                        end;

            end;

      write(q,'   ',r);

      readln;

end.

Но как видно, тут получаем переполнение при операции shl если делимое больше 127 и, соответственно, уход в зацикливание. Нужно как-то извратится, и не получать переполнение. Чтобы можно было поделить скажем 250 на 230 и тд.

PS: Для любителей деления в столбик и им сочувствующих в танках - использовать операцию деления и умножения НЕЛЬЗЯ.

Ответ: Деление 8bit на 8bit

MIDletPascal:

Код:

var

  sum,ost,a,b : integer;

begin

  a:=250;

  b:=230;

  /// a div b ///

  sum:=0;

  ost:=a;

  while (ost>=b) do

  begin

    ost:=ost-b;

    sum:=sum+1;

  end;

  drawText(''+a+' div '+b+' = '+sum+'; '+ost, 0, 0);

  repaint;        

  repeat until false;

end.

Ответ: Деление 8bit на 8bit

Спасибо за решение, пока я выкручивался так:

PHP код:


		
			
Var

 q,x,y,a,b,counter : byte;



Begin

      x := 20;      

      y := 4;       

      q := 0;       

      while x >= y do

            Begin

                  a := x shr 1;

                  b := y;

                  counter := 1;

                  while a >= b do

                        begin

                              b := b shl 1;

                              counter := counter shl 1;

                        end;

                  x := x - b;

                  q := q + counter;

            End;

      Debug(0,0,q);        {Print result X DIV Y}

end.

Но похоже что твое решение намного быстрее. Щаз скоро проверим. Спасибо.