LINUX.ORG.RU
Форум — Talks  

[Вещества] Можно ли выразить всю математику только через битовые операции?

 


0

2

Дано: <<, >>, |<<, >>| (типа циклические сдвиги), ~, &, |, ^.

Можно ли выразить все математические операции типа +, -, *, / через битовые операции?

Тред о веществах, поэтому в Talks.

И да, я использую Linux.

 ← 1 2 →

какие только люди не живут.

vvff
()
Ответ на: комментарий от dn2010

А, так вы могли написать этот код: 

#include <iostream>

using namespace std;

int sum(int a, int b){
    return (!a||!b ? a|b : sum((a&b)<<1,a^b));
}

int main(){
    int a, b;
    cin >> a >> b;
    cout << sum(a,b);
    return 0;
}
не задумываясь и с ходу? Чего ж не написали? И да, раз уж вы у нас разбираетесь, может поделитесь умножением и делением, да для float-значений?

AlexCones ★★★
() автор топика
Ответ на: комментарий от shquark

У меня вообще нет способа, поэтому спрашиваю.

AlexCones ★★★
() автор топика

Почему ты так плохо учишься в своей школе?

mopsene ★★★
()

Можно ли выразить все математические операции типа +, -, *, / через битовые операции?

Только если у нас будет еще if (или тернарный оператор или другое средство), позволяющий сравнивать результат некоторого битвого выражения с нулем. Если нет - никак.

Deleted
()

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

iVS ★★★★★
()
Ответ на: комментарий от Deleted

А разве If не может быть построен на основе такой же логики?

// Хоть один адекватный человек в треде.

AlexCones ★★★
() автор топика
Ответ на: комментарий от DNA_Seq

Хорошо, приведу пример.

Когда то я писал код для трехмерной отрисовки куба. При этом код должен был включать в себя размещение точек в пространстве для каждой грани. Можно было сделать через for-ы: http://pastebin.com/cTj10DAi , я подумал и сделал через логику: http://pastebin.com/QR9t4vMZ . (Можно еще в два раза сократить, отделил переменные для читабельности.) По сути в данной ситуации я сделал if на логике. Generic-версию разве нельзя как-то соорудить?

AlexCones ★★★
() автор топика
Ответ на: комментарий от provaton

В брейнфаке есть полноценный инкремент и декремент. А вот smallfuck уже оперирует отдельными битами.

PolarFox ★★★★★
()
Ответ на: комментарий от Deleted

Если будет сравнение с нулем, то как-то так: (код не запускал, из головы) 

unsigned sum(unsigned a, unsigned b)
{
    if(!a && !b)return 0;
    unsigned lba = a & 1, lbb = b & 1;
    if(lba && lbb) return sum(sum(1, a >> 1), b >> 1) << 1;
    else return lba | lbb | (sum(a >> 1, b >> 1) << 1);
}
unsigned sub(unsigned a, unsigned b)
{
    if(!a && !b)return 0;
    unsigned lba = a & 1, lbb = b & 1;
    if(!lba && lbb) return (sub(sub(a >> 1, 1), b >> 1) << 1) | 1;
    else return lba ^ lbb | (sub(a >> 1, b >> 1) << 1);
}

Deleted
()
Ответ на: комментарий от Kosyak

Однако, там мултиплексоры есть (тот самый аналог if)

Kosyak ★★★★
()
Ответ на: комментарий от Deleted

Умножение: 

unsigned mul(unsigned a, unsigned b)
{
	if(!a || !b)return 0;
	unsigned lbb = b & 1;
	if(lbb) return sum(a, mul(a, b >> 1) << 1);
	else return mul(a, b >> 1) << 1;
}
Насиловать мозг делением лень.

Deleted
()

man Компьютерная арифметика

observer ★★★
()

AlexCones

Можно ли выразить все математические операции типа +, -, *, / через битовые операции?

можно. для этого необходимо и достаточно всего одного эл-та и-не. (одного типа эл-тов точнее. Самих эл-тов надо конечно Over9000).

drBatty ★★
()
Ответ на: комментарий от Deleted

franchukroman

Что не так?

на кой хрен тут рекурсия, да ещё и хвостовая? Сделать цикл не судьба было? Это не LISP, это ваще-то C, тут ваши функциональные какашки никто подбирать не обязан. И не будет, в реальных, хоть чуть более сложных случаях. Как вы сами признались - написать тривиальную дихотомию (деление), это для вас уже

Насиловать мозг

как и практически любой другой реальный алгоритм.

drBatty ★★
()
Ответ на: комментарий от Deleted 
bool eq(unsigned a, unsigned b)
{
	return !(a ^ b);
}
bool less_num(unsigned a, unsigned b); // a < b
bool less_or_eq(unsigned a, unsigned b) // a <= b
{
	if(eq(a, b))return true;
	unsigned lba = a & 1, lbb = b & 1;
	if(less_num(a >> 1, b >> 1)) return true;
	else return eq(a >> 1, b >> 1) && !(!lbb && lba);
}
bool less_num(unsigned a, unsigned b) // a < b
{
	return less_or_eq(a, b) && !eq(b, a);
}
unsigned div_helper(unsigned a, unsigned b, unsigned l, unsigned r)
{
	if(!sub(r, l))return 0;
	if(sub(r, l) == 1)
	{
		if(less_or_eq(mul(r, b), a))return r;
		else return l;
	}
	unsigned m = sum(l, r) >> 1;
	if(eq(mul(m, b), a))return m;
	else if(less_num(mul(m, b), a)) return div_helper(a, b, m, r);
	else return div_helper(a, b, l, m);
}
unsigned div(unsigned a, unsigned b)
{
	return div_helper(a, b, 0, a);
}

Написал деление. Самым примитивным способом - бинарным поиском.

Deleted
()
Ответ на: комментарий от drBatty

на кой хрен тут рекурсия, да ещё и хвостовая?

Естественно, в реальной задаче я писал бы циклы.

А здесь рекурсия потому, что:

1) старался реализовать, как говорил ТС, минимальными средствами языка.

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

тут ваши функциональные какашки никто подбирать не обязан

Я не пишу на функциональных ЯП, ибо они непрактичны. Сколько раз мне придется еще повторить эту фразу на ЛОРе? А какашка потому, что так пожелал ТС.

Как вы сами признались - написать тривиальную дихотомию (деление), это для вас уже

Насиловать мозг

Тривиальная дихотомия сразу под твоим гневным мессагом.

как и практически любой другой реальный алгоритм.

Oh really? http://codeforces.ru/profile/frp http://acmp.ru/index.asp?main=user&id=8449 http://informatics.mccme.ru/moodle/submits/view.php?user_id=18777#1 http://acm.timus.ru/author.aspx?id=89430 http://www.e-olimp.com/users-result/7378

Deleted
()
Ответ на: комментарий от Deleted

franchukroman

1) старался реализовать, как говорил ТС, минимальными средствами языка.

эх... это по твоему «минимальные средства»?

franchukroman

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

если мы реализуем умножение, очевидно сложение у нас уже есть. Делать вид, что его «нету», и что CALL & RET это не оно - подтасовка фактов.

franchukroman

Сколько раз мне придется еще повторить эту фразу на ЛОРе? А какашка потому, что так пожелал ТС

да? я его понял по другому, не настолько буквально.

franchukroman

Тривиальная дихотомия сразу под твоим гневным мессагом.

(:
ИМХО BSDM это, а не дихотомия. Кстати, быстрее и попроще будет деление без восстановления остатка. Одним простым циклом. Куда как проще и дешевле сделать простенький аппаратный сумматор/инкрементатор для целых чисел, что-бы строить циклы для умножения/деления и прочего. Делать это всё программно, да ещё и в стеке... Ну как-то странно. Да и не было такой задачи.

franchukroman

Oh really? http://codeforces.ru/profile/frp http://acmp.ru/index.asp?main=user&id=8449 http://informatics.mccme.ru/moodle/submits/view.php?user_id=18777#1 http://acm.timus.ru/author.aspx?id=89430 http://www.e-olimp.com/users-result/7378

для Ъ можно? к чему это?

drBatty ★★
()
Ответ на: комментарий от drBatty

я его понял по другому, не настолько буквально.

Ну я понял буквально. Если ТС не это имел ввиду, значит, он плохо изложил свою мысль.

для Ъ можно? к чему это?

К моему «неумению» писать дихотомию, как и другой тривиальный алгоритм. Для Ъ: по ссылкам мои профили на сайтах, относящихся к спортивному программированию.

Deleted
()
Ответ на: комментарий от Deleted 
def inc(a):
    if a&1 and a^(-1): return inc(a>>1)<<1
    return a^(not a&1 or -1)

def add(a,b):
    if b: return add(inc(a),-inc(-b))
    return a

def div(a,b):
    if a>=0: return inc(div(-add(-a,b),b))
    return -1
alfix ★
()
Ответ на: комментарий от AlexCones

В частных можно, в общих - нельзя. Man полнота по Тьюрингу.

DNA_Seq ★★☆☆☆
()
Ответ на: комментарий от Deleted

я что-то туплю? это что значит? http://acm.timus.ru/status.aspx?space=1&num=1000&author=89430

1000. A+B Problem
Ограничение времени: 1.0 секунды
Ограничение памяти: 16 МБ
Вычислите a+b
Исходные данные
a и b
Результат
a+b
Пример
исходные данные результат

1 5

6

Подсказка
Используйте +
Автор задачи: Павел Атнашев

да... A+B Problem это конечно сильно... А вообще, я этого вашего «спортивного программирования» даже в детстве не понимал, когда участвовал в олимпиадах.

drBatty ★★
()
Ответ на: комментарий от Deleted

franchukroman

К моему «неумению» писать дихотомию, как и другой тривиальный алгоритм.

ты, кстати, немного не понял - речь не про «неумение». Я дихотомию и на brainfuck могу написать, и на sed. Но не буду, ибо «насилие мосга». Так и тут - делать наивный вид, что инкремент/декремент у нас система не умеет, а вот функции она умеет - довольно глупо, или ты таки не знаешь, как реализованы функции? Если такой правильный - давай без функций. Или рассказывай, как в твоём CPU вызов функции реализован без декремента.

drBatty ★★
()
Ответ на: комментарий от drBatty

Хватит шланговать. A+B нужна только чтобы попробовать и ознакомиться с сайтом.

Отсортируем на том же тимусе задачи по возрастанию сложности и смотри с конца.

http://acm.timus.ru/problem.aspx?space=1&num=1529

http://acm.timus.ru/problem.aspx?space=1&num=1622

http://acm.timus.ru/problem.aspx?space=1&num=1540

...

Deleted
()

Всё, что происходит внутри микропроцессора сводится к простым битовым операциям, других ещё не придумали. С другой стороны, это - ещё не «вся математика».

Deleted
()
Ответ на: комментарий от Deleted

renjumin

Всё, что происходит внутри микропроцессора сводится к простым битовым операциям

Кроме датчика ГСЧ, который использует физические процессы.

Deleted
()
Ответ на: комментарий от drBatty

Для сложения без циклов и функций придется 32 раза написать одно и то же :) (т.к. для инкремента нужно сложение). Мне лень.

Но если так подходить, то мы не имеем права создавать локальные переменные, т.к. для них тоже нужен декремент sp/esp/rsp. Но если подходить так, то и на C мы не имеем права писать, т.к. main - тоже функция, и для ее вызова делается декремент sp/esp/rsp. И ввод-вывод не имеем права делать, т.к. для этого нужно звать либо libc, либо int 0x80, что требует декремента. Итого, на 100% правильно без скрытых декрементов мы сделать не можем ВООБЩЕ НИЧЕГО :)

Deleted
()
Ответ на: комментарий от Deleted

franchukroman

http://acm.timus.ru/problem.aspx?space=1&num=1529
http://acm.timus.ru/problem.aspx?space=1&num=1622
http://acm.timus.ru/problem.aspx?space=1&num=1540

почему сам текст не перевели? где там твой код? давал-бы сразу ссылку на задачу и на своё решение. Ты дал ссылку на 100500 задач. Типа «здесь есть мои решения!». Я должен их там искать? Учитывая, что у тебя ещё и ники везде разные? Кто из нас шлангует? Я, блин, не из ОК, если кто не понял, и никаких собеседований на ЛОРе не устраиваю. Если мне что-то не нравится в коде - я об этом прямо и говорю.

drBatty ★★
()
Ответ на: комментарий от Deleted

franchukroman

Для сложения без циклов и функций придется 32 раза написать одно и то же :) (т.к. для инкремента нужно сложение). Мне лень.

ага. потому мы сделали вид, что у нас «без инкрементов», используя функцию. Так вот немного подделали условие. Ну вот теперь рассказывай, каким таким волшебным образом у тебя получилось сделать вложенные функции без сложения/вычитания?

franchukroman

Но если так подходить, то мы не имеем права создавать локальные переменные

да, конечно. Хотя, если функции не являются рекурсивными, то вполне таки можно считать и даже делать переменные статическими.

franchukroman

Но если подходить так, то и на C мы не имеем права писать, т.к. main - тоже функция, и для ее вызова делается декремент sp/esp/rsp.

это к алгоритму задачи никак не относится. Функция main вполне может запускаться даже на машинах без стека. Остальные «функции» тоже - они могут транслироваться в абсолютные адреса или даже инлайнится. Но вот твои рекурсивные функции под такое определение совсем не подходят.

franchukroman

Итого, на 100% правильно без скрытых декрементов мы сделать не можем ВООБЩЕ НИЧЕГО :)

я помнится писал программу без всякого стека. Было сложно, но далеко не невозможно. И да, в своё время одна суперкорпорация вообще против стека выступала... Она даже сейчас ещё жива.

drBatty ★★
()
Ответ на: комментарий от drBatty

я помнится писал программу без всякого стека.

Если она была на ассемблере и работала на голом железе, то с этим нет никаких проблем (но нужно сейчас это только в embedded). Иначе на 100% избежать использования стека невозможно.

Относительно рекурсии: если нужна абсолютная чистота, то я уже говорил: единственный путь ее получить - продублировать код для каждого бита. Мне банально лень.

Deleted
()

man RISC

BTW минимальный базис для бинарных операций - вообще (|, ^) или (&, ^).

На их основе строится интерпретатор брейнфака (удобства ради, машина Тьюринга требует бесконечной ленты, ЕМНИП), на котором пишется человекоподобный ИИ, заполняется базовыми аксиомами и понятиями и обучается на матфаке. После чего в его памяти будет находиться вся (sic!) математика, выраженная через битовые операции.

schizoid ★★★
()
Ответ на: комментарий от Deleted

Что бы мог значить последний смайлик?

Он то и значит, что он (как предшествующий ему текст) ничего не значит :D

moscwich ★
()
Ответ на: комментарий от schizoid

В брейнфаке битовых операций нет вообще: там есть только +-<>.,[] (инкремент, декремент, сдвиг указателя влево, сдвиг указателя вправо, ввод символа с клавиатуры и сохранение его в ячейку, на которую указывает указатель, вывод символа, на который указывает указатель, на экран, начало цикла «пока текущая ячейка не ноль», конец цикла «пока текущая ячейка не ноль»).

Deleted
()
Ответ на: комментарий от moscwich

Да, пожалуй, в этом треде я уже таки КЭП :)

Deleted
()
Ответ на: комментарий от Deleted

franchukroman

Если она была на ассемблере и работала на голом железе, то с этим нет никаких проблем (но нужно сейчас это только в embedded). Иначе на 100% избежать использования стека невозможно.

ну почему так трагично? С с таким справляется. Правда криво, но всё равно.

franchukroman

Относительно рекурсии: если нужна абсолютная чистота, то я уже говорил: единственный путь ее получить - продублировать код для каждого бита. Мне банально лень.

да... Настоящая и Ъ жена === девственница. То, что она работала 10 лет на трассе делая минет и даваясь в задницу - в принципе мелочь: девственная плева-то цела! Операции по восстановлению мы тоже не учитываем, хотя стоят они не так уж и дорого...

drBatty ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2 →
Talks