VPF::Суммирование и умножение чисел

ne0n

Дата 8.10.2008, 00:55 (ссылка)

(нет голосов)

Загрузка ...

PlayBoy

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 5.8.2005
Где: Н.Новгород

Репутация: 1
Всего: 11

Вообщем задача - надо сложить или умножить числа используя только битовые операции над ними, в случаи с умножением будет проще, если написать функцию сложения smile

буду очень благодарен если кто подкинет информации по этому поводу!

--------------------

http://sa-sec.org
как я вам? smile

morpheyushka

Дата 8.10.2008, 10:30 (ссылка)

(голосов:6)

Загрузка ...

Зеленый человек

Профиль
Группа: Участник
Сообщений: 563
Регистрация: 26.2.2008
Где: Киев

Репутация: 3
Всего: 8

я такое когда то на ассемблере делал, причем числа вылазили за регистры)))

--------------------

Спасибо делается вот так!!!

ne0n

Дата 9.10.2008, 18:17 (ссылка)

(нет голосов)

Загрузка ...

PlayBoy

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 5.8.2005
Где: Н.Новгород

Репутация: 1
Всего: 11

ммм неушто ни укого нет идей?)

--------------------

http://sa-sec.org
как я вам? smile

Albinos_x

Дата 9.10.2008, 22:36 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 26
Всего: 108

использование циклов и условий допускается?

Это сообщение отредактировал(а) Albinos_x - 9.10.2008, 22:49

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

ne0n

Дата 9.10.2008, 22:58 (ссылка)

(нет голосов)

Загрузка ...

PlayBoy

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 5.8.2005
Где: Н.Новгород

Репутация: 1
Всего: 11

Albinos_x да

Это сообщение отредактировал(а) ne0n - 9.10.2008, 22:59

--------------------

http://sa-sec.org
как я вам? smile

Albinos_x

Дата 9.10.2008, 23:18 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 26
Всего: 108

Код


function BitSumm(A,B:Integer):Integer;
var c:integer;
begin
repeat
 c:=a xor b;
 b:=(a and b) shl 1;
 a:=c;
until b=0;
result:=a;
end;

Добавлено через 8 минут и 50 секунд
сейчас над умножением подумаю

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

ne0n

Дата 9.10.2008, 23:35 (ссылка)

(нет голосов)

Загрузка ...

PlayBoy

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 5.8.2005
Где: Н.Новгород

Репутация: 1
Всего: 11

Albinos_x, Большое спасибо за сложение....я уже начал писать свой алго-некое подобие сложение столбиком....но втой вариант просто супер) даже со знаковыми числами корректно работает^_^. Тока теперь надо поянть ка кэто работает)

--------------------

http://sa-sec.org
как я вам? smile

Albinos_x

Дата 9.10.2008, 23:38 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 26
Всего: 108

не... над умножением думать не надо.. запускать в цикле сложение и всё...)))

Добавлено через 7 минут и 3 секунды
ne0n, всё просто, операция xor производит складывание побитовое, но не может перенести разряды при попадании на 1+1, для выделения таких разрядов использую and, но т.к. эти разряды перейдут в старшие, то делаю сдвиг на один и опять складываю это число с результатом, и так пока в старщие разряды не будет переходить ни одного разряда ...)

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

ne0n

Дата 9.10.2008, 23:47 (ссылка)

(нет голосов)

Загрузка ...

PlayBoy

Профиль
Группа: Участник
Сообщений: 733
Регистрация: 5.8.2005
Где: Н.Новгород

Репутация: 1
Всего: 11

Цитата(Albinos_x @ 9.10.2008, 23:38

)

не... над умножением думать не надо.. запускать в цикле сложение и всё...)))

ога, я про это уже писал....что если научиться складывать - то умножать будет не проблема)

Добавлено через 12 минут и 45 секунд
Albinos_x, с меня еще +, за элегантное решение) я кстати сначало тоже начал капать в эту сторону....ну чтото не сообразил...и решил в лоб столбиком все посчитать, но твое решение smile

просто шикарное! smile

--------------------

http://sa-sec.org
как я вам? smile

Albinos_x

Дата 10.10.2008, 00:15 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 26
Всего: 108

ne0n, просто я сначала подумал, для умножения тоже чтонибудь хитроумное smile

, например через сдвиги сделать, но потом решил smile

, что так просто не выйдет... smile

Это сообщение отредактировал(а) Albinos_x - 10.10.2008, 00:17

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

skyboy

Дата 10.10.2008, 00:27 (ссылка)

(нет голосов)

Загрузка ...

неОпытный

Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 4
Всего: 260

Цитата(Albinos_x @ 9.10.2008, 23:15

)

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

абсолютно напрасно. сдвиг - это что? верно: деление или умножение на два.
двойной сдвиг влево - умножение на 4.
тройной - на 8.
если свдинуть единожды и сложить(сложение уже описали) с результатом двойного сдвига, то выйдет 2x + 4x = 6x: умножение на 6.
а можно так: 2 * ( 2 * х + х) - то есть сдвинуть влево, сложить с исходным числом и сдвинуть влево биты результата.

Добавлено через 27 секунд

Цитата(skyboy @ 9.10.2008, 23:27

)

абсолютно напрасно.

в смысле, напрасно думал, что "так просто не выйдет" smile

Albinos_x

Дата 10.10.2008, 01:26 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 26
Всего: 108

это будет слишком громоздко, и далеко не эффективней складывания в цикле, т.к. появится куча условий и временных переменных, т.к. придётся сначала искать ближайшее кратное нашим разрядам, после сдвига вычитать уже сделанное, потом опять искать кратное, потом складывать...

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

Albinos_x

Дата 10.10.2008, 03:44 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 26
Всего: 108

это будет выглядить где-то так:

Код


function BitPowNO(A,B:Integer):Integer;
var c,d:integer;
begin
Result:=0;
c:=1;
d:=0;
repeat
   if (b and c)=c then
      Result:=BitSumm(Result, (a shl d));
   c:=c shl 1;
   d:=BitSumm(d, 1);
   until (b shr d)=0;
end;

функция будет эффективней складывания в цикле приблизительно при b>2n+k, где n-число разрядов в числе b, k - число единичных разрядов в числе b.

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Delphi: Общие вопросы \| Следующая тема »