Задача на расстояние между двоичными кодами, Помогите с решением плииз Опции

[Lodar']

Расстоянием между двоичными кодами называется количество несовпадающих двоичных разрядов. Например:
0101101
0010101 р=3
-----------
***
Составить функцию Ro (N1,N2), вычисляющую расстояние между двоичными представлениями её целочисленных аргументов N1 N2

Добавлено через 1 мин.
желательно написать самый рациональный алгоритм (язык Delphi консольное приложение)

[volvo]

Желательно пользоваться поиском, кстати:
задача на паскале:составить функцию

[Lodar']

тот алгоритм на кторый вы дали ссылку мне не очень понятен. Вот мой алгоритм: на вход подается 2 целочисленных числа, переводим каждое в двоичный код и запихиваем в 2 массива. Потом начинаем в цикле сравнивать, если не совпадает то счетчик +1. как вы думаете это рабочий алгоритм? если да то помогите с реализацией пожалуйста!))

[Lodar']

Вот прога которую я написал. но она почему то не работает подскажите гда ошибка?

program Project1;

{$APPTYPE CONSOLE}
uses
  SysUtils;
type
  TIntarr=array [1..100] of integer;
var q,n1,n2:integer;
Function Ras (N1,N2:integer):integer;
  function Perevod (var n:integer):TIntarr;
  var s,i,l,k:integer;
      a,b:TIntarr;
   Begin
    k:=0;
    while N>=1 do
      begin
       a[i]:=(N mod 2);
       N:=(N div 2);
       I:=i+1;
      end;
    l:=i;
     while i<>1 do
      begin
       b[k]:=a[i-1];
       i:=i-1;
       k:=k+1;
      end;
    b[l-1]:=a[1];
    Result:=b;
   end;
var a1,a2:TIntarr;
    i,t:integer;
begin
  a1:=Perevod (n1);
  a2:=Perevod (n2);
  for i:=1 to 100 do
    if a1[i]<>a2[i] then
    t:=t+1;
 result:=t
end;
begin
 Writeln ('vvedi chisla');
 REadln (n1,n2);
 q:=ras(n1,n2);
 Writeln (q);
 readln; { TODO -oUser -cConsole Main : Insert code here }
end.

Сообщение отредактировано: Lodar' - 29.01.2009 3:21

[volvo]

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

Рабочий? Да. Рациональный? Нет... Поскольку речь шла о рациональном изначально, то твой алгоритм я предпочитаю не реализовывать... Там битовые операции, выполняется очень быстро, компактный код, здесь - лишние массивы... Что именно непонятно ТАМ?

Добавлено через 6 мин.

она почему то не работает подскажите гда ошибка?

Ошибка - в неинициализированных переменных... I внутри процедуры Perevod чему равен, можно узнать? К какому элементу массива ты обращаешься?

[Lodar']

ну я так понял что на вход подаются 2 числа типа Integer. Как перейти к битам? и, если можно, то рассшифровать вот эти строки функции

inc(res, (n1 and $1) xor (n2 and $1));
    n1 := n1 shr 1; n2 := n2 shr 1;

[amega]

непроще воспользоватся inttoBin функцией, или ее в паскале нет?

Сообщение отредактировано: amega - 29.01.2009 2:31

[Lodar']

непроще воспользоватся inttoBin функцией

ну я не знаю как =))) да и это я так понял не особо важно

Добавлено через 5 мин.

Ошибка - в неинициализированных переменных... I внутри процедуры Perevod чему равен, можно узнать? К какому элементу массива ты обращаешься?

поставил i:=1;
прога запускается но выдает неправильный ответ( в чем дело? пришлите пожайлуста откомпилированный текст проги если не сложно?

[Lodar']

и еще огромная просьба обьяснить ту рациональную функцию. Выше я написал че не понятно

[Lodar']

мне если можно то побыстрее) завтра уже сдавать((( заранее благодарен!

[volvo]

я так понял что на вход подаются 2 числа типа Integer. Как перейти к битам?

Число типа Integer - это 32-битное (для Дельфи) целое, правда? И хранится оно в двоичном коде. Скажем, 12 представлено в памяти как 00000000000000000000000000001100, а 13 - как 00000000000000000000000000001101. Так вот, это все - биты, как ты уже догадался, потому как их ровно 32. Теперь, как получить доступ к отдельным битам: проще всего использовать операцию "Битовый AND", которая берет и делает их побитное "умножение" (ну да, And - умножение, а Or - сложение, так уж повелось): (0 and 0) = (0 and 1) = (1 and 0) = 0, и только если оба бита равны 1, то и результат операции And будет единичным: (1 and 1) = 1...

Еще не догадался, как получить содержимое самого младшего бита в числе? Правильно, надо это число "умножить" на маску, состоящую из всех 0, и одной единицы, в том бите, который мы проверяем... Тогда без разницы, что было в первых 31 битах, там после And-а все равно будут нули, а вот состояние последнего бита, маска которого содержит 1, мы узнаем...

Вот и делаем:
00000000000000000000000000001100
and
00000000000000000000000000000001
=
00000000000000000000000000000000 = 0₁₀, то есть в числе 12 младший бит НЕ установлен. А в числе 13 - установлен, поэтому
00000000000000000000000000001101
and
00000000000000000000000000000001
=
00000000000000000000000000000001 = 1₁₀.

Теперь о том, что значит

inc(res, (n1 and $1) xor (n2 and $1));

(n1 and $1) - это выявление младшего бита первого числа
(n2 and $1) - младший бит второго числа

XOR - еще одна битовая операция, которая возвращает: (1 xor 0) = (0 xor 1) = 1,
а при равных битах: (0 xor 0) = (1 xor 1) = 0, то есть, если младшие биты обоих чисел НЕодинаковы, то
(n1 and $1) xor (n2 and $1) будет = 1. Если одинаковы - будет равно 0... Ну, и последний этап: просто увеличиваем счетчик на это число, если биты разные, счетчик увеличится на 1, если одинаковые - счетчик увеличится на 0, а значит, ничего не изменится... Это то, что и нужно - подсчитывать - то надо те биты, которые различаются...

Ну, и после того, как младшие биты проверены, надо оба числа сдвинуть вправо, чтобы проверить новую пару бит, это и делается через

n1 := n1 shr 1; n2 := n2 shr 1;

- битовый сдвиг на 1 вправо... Проверяем таким образом все 32 пары бит, и в переменной Res имеем число несовпадающих бит в числах.

Тебе надо почитать о битовых операциях (OR, AND, XOR, NOT, SHR, SHL), если ты действительно хочешь в этом разобраться.

[Lodar']

Спасибо большое! а мою прогу можете исправить? я вроде все правильно реализовал..но считает она неправильно почему то(((

[volvo]

мне если можно то побыстрее) завтра уже сдавать(((

Ну, знаешь, это как-то не наши проблемы. Сам дотянул, а теперь тебе срочно надо... Ну, надо - так разбирайся:

program diff;

{$APPTYPE CONSOLE}
uses
  SysUtils;

const
  size = 32;
type
  TIntarr=array[1 .. size] of integer;

Function Ras(n1, n2: integer): integer;

  function Perevod(n: integer): TIntarr;
  var i: integer;
  begin
    FillChar(result, sizeof(Tintarr), 0);
    i := 0;
    while n <> 0 do begin
      inc(i);
      result[i] := n mod 2;
      n := n div 2;
    end;
    // все остальное - выброшено, потому что не важен порядок чисел,
    // если A1 будет "перевернут", то и A2 - тоже, а значит, все будет работать
  end;

var
  a1, a2: TIntarr;
  i: integer;
begin
  result := 0;
  a1 := Perevod(n1);
  a2 := Perevod(n2);
  for i := 1 to size do
    if a1[i] <> a2[i] then result := result + 1;
end;

var
  n1, n2: integer;

begin
  Writeln ('vvedi chisla');
  Readln(n1, n2);
  Writeln(ras(n1,n2));
  Readln;
end.

[Lodar']

ой спасибо) а вот ворпос (n1 and $1) что здесь $ означает?

[Lodar']

и непонятно что вот это за строчка еще

FillChar(result, sizeof(Tintarr), 0);

если можно поясните пожайлуста

Сообщение отредактировано: Lodar' - 29.01.2009 4:38

[volvo]

(n1 and $1) что здесь $ означает?

Вообще-то $ перед числом означает, что это число записано в 16-ричной системе счисления. Здесь можно было бы и просто 1 поставить, но это уже привычка: как только дело касается битовых операций (and/or/xor), я обязательно пишу все числа в 16-ричной с/с.

непонятно что вот это за строчка еще

У тебя Хелпа нет что-ли? Это заполнение нулями всей переменной result, начальная инициализация, чтоб там всякий мусор не остался...

[Lodar']

Cпасибо большое! я разобрался)))) вы мне очень помогли!

[Lodar']

Хм...а с отрицательными числами будет прога работать? подскажите пожалуйста!

[volvo]

а с отрицательными числами будет прога работать?

Моя функция (ссылка во втором посте) - будет, твоя - нет. Я тебе говорил, что работать надо с битами? Говорил. Вот тебе и результат: моей функции совершенно все равно, положительное число или отрицательное, а твоей - есть огромная разница.

[Lodar']

=)) твой вариант несовсем прокатил на экзамене(( препод сказал что он маленько не рационален...ну поставил мне конечно 4,5 =) все равно спасибо большое за помощь! я могу показать где что довести до идеала если интересно

Добавлено через 12 мин.
вобщем там не надо было умножать на маску. Было предложено просто сделать операцию XOR над числами N1 и N2 (причем один раз а не в цикле) и посчитать где вылазит 0

Сообщение отредактировано: Lodar' - 1.02.2009 15:29