Помогите расшифровать код, не понимаю, что он значит, т.к. С знаю не очень, а разобраться необходимо.

Вот фрагменты кода:
Пример 1:
unsigned long u;
u=23;
while (u) {...} Что означает условие в While?

Пример 2:
unsigned long u;
u=23;
if(u&1) {...} Что означает условие в If?

Пример 3:
unsigned long u;
u=23;
u>>1; Что означает это действие?

Помогите, пожалуйста!

•  Пока u не равно нулю
•  Проверка на нечетность
•  Деление на 2

вот с if у меня вопрос, почему это проверка на нечетность? мне казалось что это вернет единицу только когда все биты числа u равны единице т.е. u будет иметь совершенно конкретное значение. 
Любопытно просто, учусь)

На самом деле if вернет единицу, если младший бит равен единице. А все целые числа, у которых младший бит 1 являются нечетными.

Это сообщение отредактировал(а) creatorcode - 26.4.2008, 23:02

точно! теперь поняла, спасибо!

на всякий случай в расширенном виде:
х>>n  // деление на 2 в степени n
х<<n //  умножение на 2 в степени n 
//Примечание: только для целочисленных простых  типов


Это сообщение отредактировал(а) mes - 27.4.2008, 00:29

mes, спасибо, это как раз недавно прошли)))
операторы которые сдвигают биты либо влево либо вправо. Правда не понимаю зачем нужно ТАК делить на 2 если можно u/2 сделать...

Спасибо большое всем за ответы, очень помогло!

Это сообщение отредактировал(а) SashaOSC - 27.4.2008, 09:25

Современные компиляторы при оптимизации сами вместо u/2 подставляют u>>1
поэтому сейчас это традиция, которая пришла из тех давних времен, когда скорость работы программы была очень важным фактором, так как компьютеры были очень медленные, а компиляторы глупые.. в  1990 году частота проца пк была в около 20-30Мгц. Ну а те что были в школах и институтах имели всего 2-3Мгц ))
тогда экономили на каждой операции. Например для подсчета позиции в памяти координаты на экране в графическом режиме (n=x+y*320 )(разрешение экрана 320х200х256 было тогда еше в почете, хотя уже были и svga) делали так: n=x+(y<<8)+(y<<6);
а на асме даже обнуление делали посредстом "исключаещего ИЛИ" ( XOR ah,ah )

P.S. деление посредством сдвига более наглядно - так как не заставляет думать о возможном округлении




Это сообщение отредактировал(а) mes - 27.4.2008, 23:27

А вот ещё один пример:

unsigned long u;
u=23;
if (1^(u&1)) {...}

Что означает это условие?

Проверка на четность

А чем отличается 
if (1^(u&1)) {...}
от
if (u&1) {...}
?

u >> 1

это рекомендуемый интелом метод обнуления регистра
он и сейчас в силе


условие избыточно
а вообще, проверка на четность

Добавлено через 1 минуту и 4 секунды

второй - проверка на нечетность

Помогите портировать функцию из C в Delphi пожалуйста!

unsigned long qe2(unsigned long x, unsigned long y, unsigned long n) {
unsigned long s, t, u;
int i;
s=1; t=x; u=y;
while (u) {
if(u&1) s=(s*t)%n;
u>>1;
t=(t*t)%n;
}
return(s)

У меня получилось примерно так:

function TForm1.qe2(x:Cardinal;y:Cardinal;n:Cardinal):Cardinal;
Var
    s,t,u:Cardinal;
Begin
    s:=1; t:=x; u:=y;
    While u<>0 Do
        Begin
          If (Round(u) mod 2)=1 Then
              s:=(s*t) mod n;
          u:=Round(u/2);
          t:=(t*t) mod n;
        End;
    qe2:=s;
End;

а Работает? Я в Дельфях да Паскалях НУЛЬ полнейший, но разве там не procedure, а function? Интересно, интересно...
И вообще думаю это должна быть отдельная тема, это во-первых, а во-вторых это должно быть в специальном разделе "Delphi, Kylix, Pascal".

В Паскале/Делфи есть и процедуры и функции.
Функции возвращают некоторое значение, а процедуры нет.

В коде на Си есть ошибка – зацикливание, т.к. u не изменяется (результат u>>1 никуда не записывается). Если я правильно понял, как надо правильно было это пофиксить, то:






Какая разница? В том разделе меньше людей которые знают Си, в этом Pascal. 

сорри..недоглядел..исправлю

Добавлено через 4 минуты и 44 секунды

прочитать легче, чем написать 
то есть намного вероятнее что правильно переведет тебе прогу в паскаль человек который слегка знает с++(так как ему надо лишь понять условие)
чем тот который слегка знает паскаль (ведь ему надо построить правильный код).   

На самом деле это реализация алгоритма цепочки сложений, или метода двоичных квадратов и умножения:
rez=x^y mod n
(например, rez=23^25 mod 45=23, ни один тип данных такие числа не вмещает)
Только этот код работает совершенно неправильно!
У меня нет возможности проверить оригинал на Си, может кто-нибудь проверит?
Результат проверять на виндозном калькуляторе инженерного вида.

Есть альтернативный алгоритм с рекурсией,но он тоже не работает :(

unsigned long fast_exp (unsigned long x, unsigned long y, unsigned long n) {
unsigned long tmp;
  If (y==1) return(x%n);
  If (1^(x&1)) {
      tmp=fast_exp(x,y/2,n);
      return ((tmp*tmp) % n);}
  Else {
      tmp=fast_exp(x,(y-1)/2,n);
      tmp=(tmp*tmp) % n;
      tmp=(tmp*x) % n;
      return (tmp);
  }
}

Проверил - работает
А вот ему бы я доверять не стал - промежуточные вычисления делаются в плавающей точке, возможно несовпадение результатов.
(Хотя 23^25 mod 45=23, это тоже проверил)

Фух, сделал всё таки этот алгоритм на Delphi. Кривовато, зато работает:

function TForm1.CepochkaSlozhenii(x:Cardinal;y:Cardinal;n:Cardinal):Cardinal;
Var
  tmp1,tmp2:Cardinal;
  i:Integer;
Begin
  If y=1 Then CepochkaSlozhenii:=x mod n;
  If y=2 Then CepochkaSlozhenii:=x*x mod n;
  If y=3 Then CepochkaSlozhenii:=x*x*x mod n;
  If y>3 Then
    Begin
      If (y mod 2)=0 Then
        Begin
          tmp1:=(x*x mod n);
          tmp2:=1;
          If Round(y/2)>3 Then
            Begin
              CepochkaSlozhenii:=CepochkaSlozhenii((x*x mod n),Round(y/2),n);
              Exit;
            End;
          For i:=1 To Round(y/2) Do
            Begin
              tmp2:=tmp2*tmp1;
            End;
          CepochkaSlozhenii:=tmp2 mod n;
        End
      Else
        Begin
          tmp1:=(x*x mod n);
          tmp2:=1;
          If Round((y-1)/2)>3 Then
            Begin
              CepochkaSlozhenii:=(CepochkaSlozhenii((x*x mod n),Round((y-1)/2),n)*(x mod n)) mod n;
              Exit;
            End;
          For i:=1 To Round((y-1)/2) Do
            Begin
              tmp2:=tmp2*tmp1;
            End;
          CepochkaSlozhenii:=tmp2*x mod n;
        End;
    End;
End;

Может можно как то оптимизировать?

см ниже.

Это сообщение отредактировал(а) mes - 28.4.2008, 16:19

вроде так :


Это сообщение отредактировал(а) mes - 28.4.2008, 16:23

Вот короткий и 100% рабочий вариант:

function TForm1.CepochkaSlozhenii(x:Cardinal;y:Cardinal;n:Cardinal):Cardinal;
Var
  s,t,u:Cardinal;
Begin
  s:=1;
  t:=x;
  u:=y;
  While u<>0 Do
    Begin
      If (u mod 2)=1 Then
        s:=(s*t) mod n;
      u:=u shr 1;
      t:=(t*t) mod n;
    End;
  CepochkaSlozhenii:=s;
End;

Всем спасибо за помощь, тема закрыта.

SashaOSC, 

M MAKCim

Модератор: Пользуйтесь тегом код!