Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Помогите разобраться в коде!


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

Вот фрагменты кода:
Пример 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; Что означает это действие?

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

Автор: creatorcode 26.4.2008, 22:23
  •  Пока u не равно нулю
  •  Проверка на нечетность
  •  Деление на 2

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

Автор: creatorcode 26.4.2008, 23:01
Цитата(kalabro @  26.4.2008,  22:58 Найти цитируемый пост)
вот с if у меня вопрос, почему это проверка на нечетность? мне казалось что это вернет единицу только когда все биты числа u равны единице т.е. u будет иметь совершенно конкретное значение. 

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

Автор: kalabro 26.4.2008, 23:04
точно! теперь поняла, спасибо!

Автор: mes 27.4.2008, 00:26
Цитата(SashaOSC @  26.4.2008,  22:13 Найти цитируемый пост)
u>>1; 
Цитата(creatorcode @  26.4.2008,  22:23 Найти цитируемый пост)
 Деление на 2
Цитата(kalabro @  26.4.2008,  22:58 Найти цитируемый пост)
Любопытно просто, учусь) 

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

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

Автор: SashaOSC 27.4.2008, 09:19
Спасибо большое всем за ответы, очень помогло!

Автор: mes 27.4.2008, 09:32
Цитата(kalabro @  27.4.2008,  09:00 Найти цитируемый пост)
Правда не понимаю зачем нужно ТАК делить на 2 если можно u/2 сделать... 


Современные компиляторы при оптимизации сами вместо 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. деление посредством сдвига более наглядно - так как не заставляет думать о возможном округлении

Автор: SashaOSC 27.4.2008, 16:54
А вот ещё один пример:

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

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

Автор: creatorcode 27.4.2008, 17:16
Цитата(SashaOSC @  27.4.2008,  16:54 Найти цитируемый пост)
Что означает это условие? 

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

Автор: SashaOSC 27.4.2008, 17:48
А чем отличается 
if (1^(u&1)) {...}
от
if (u&1) {...}
?

Автор: MAKCim 27.4.2008, 17:49
Цитата(mes @  27.4.2008,  09:32 Найти цитируемый пост)
Современные компиляторы при оптимизации сами вместо u/2 подставляют u>>2

u >> 1
Цитата(mes @  27.4.2008,  09:32 Найти цитируемый пост)
а на асме даже обнуление делали посредстом "исключаещего ИЛИ"

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

Цитата(SashaOSC @  27.4.2008,  16:54 Найти цитируемый пост)
Что означает это условие? 

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

Добавлено через 1 минуту и 4 секунды
Цитата(SashaOSC @  27.4.2008,  17:48 Найти цитируемый пост)
А чем отличается 
if (1^(u&1)) {...}
от
if (u&1) {...}
? 

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

Автор: SashaOSC 27.4.2008, 17:59
Помогите портировать функцию из 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;

Автор: CppDevelopeR 27.4.2008, 21:04
Цитата(SashaOSC @  27.4.2008,  17:59 Найти цитируемый пост)
У меня получилось примерно так:

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".

Автор: THandle 27.4.2008, 21:08
Цитата(CppDevelopeR @  27.4.2008,  22:04 Найти цитируемый пост)
но разве там не procedure, а function? Интересно, интересно...


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

Автор: opjox 27.4.2008, 23:07
Цитата(SashaOSC @  27.4.2008,  17:59 Найти цитируемый пост)
Помогите портировать функцию из C в Delphi пожалуйста!


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

Код

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


Код

function qe2(x, y, n: cardinal): cardinal;
begin
  result := 1;
  while y<>0 do begin
    if(y and 1)<>0 then result := (result*x) mod n;
    y := y shr 1;
    x := (x*x) mod n;
  end;
end;


Цитата(CppDevelopeR @  27.4.2008,  21:04 Найти цитируемый пост)
это должно быть в специальном разделе "Delphi, Kylix, Pascal".

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

Автор: mes 27.4.2008, 23:26
Цитата(MAKCim @  27.4.2008,  17:49 Найти цитируемый пост)
u >> 1

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

Добавлено через 4 минуты и 44 секунды
Цитата(opjox @  27.4.2008,  23:07 Найти цитируемый пост)
Какая разница? В том разделе меньше людей которые знают Си, в этом Pascal.

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

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

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

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);
  }
}

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

Проверил - работает
Цитата

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

Автор: SashaOSC 28.4.2008, 13:35
Фух, сделал всё таки этот алгоритм на 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, 15:43
см ниже.

Автор: mes 28.4.2008, 16:17
вроде так :
Код

Var
  tmp1,tmp2:Cardinal;
  i:Integer;
 y2:Cardinal;
Begin
   if y<=3 Then
     Begin
        If y=1 Then CepochkaSlozhenii:=x mod n;
        Else If y=2 Then CepochkaSlozhenii:=x*x mod n;
        Else If y=3 Then CepochkaSlozhenii:=x*x*x mod n;
       EXIT;
     End;
   
    y2 := y SHR 2;
    If (y2>3) Then 
         If (y mod 2)=0 Then      CepochkaSlozhenii:=CepochkaSlozhenii((x*x mod n), y2,n);
         Else                                 CepochkaSlozhenii:=(CepochkaSlozhenii((x*x mod n), y2,n)*(x mod n)) mod n;  
    Else
      Begin
        tmp1:=(x*x mod n);
        tmp2:=1;

         For i:=1 To y2 Do           tmp2:=tmp2*tmp1;
      
         If (y mod 2)=0 Then       CepochkaSlozhenii:=tmp2 mod n;
         Else                                  CepochkaSlozhenii:=tmp2*x mod n;
        End
End

Автор: SashaOSC 28.4.2008, 18:19
Вот короткий и 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;

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

Автор: MAKCim 28.4.2008, 18:39
SashaOSC, 

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)