задачка: делимость на три
Dmitry Grebeniuk
Мне подкинули задачку. Категория "битовый онанизм". Практической ценности
почти не имеет, разве что моск размять.
Дан язык C. Hаписать функцию, принимающую один аргумент, являющийся
восьмибитным числом (либо 8-битный тип, либо больше, но ненулевыми могут быть
только младшие 8 бит), и возвращающую 0, не аргумент делится на 3, и "не 0"
если делится. При этом разрешено использовать только такие операции: сложение,
битовые сдвиги, логические and, or, битовые and, or, xor и целочисленные
сравнения, и только такие возможности языка, как определение локальных
переменных, чтение аргумента и переменных, модификация переменных, возврат
значения из функции. (конечно, среди доступных операций нет ни деления, ни
взятия остатка, а среди возможностей языка нет возможности подсмотреть в
табличку, иначе было бы не комуфло)
Если кто читал Кнута или из других источников знает хорошее решение, прошу не
подсказывать. Пусть люди помучаются. (хотя вот я не помню точно, есть ли у
Кнута решение, или там только намёк на него)
Пиписькомерка -- количество и вид операций. Hапример, мой самый первый
вариант имел такие характеристики: "сдвиги: 7, сложения: 8, битовые and: 8,
битовые xor: 1, логические or: 2, сравнения: 3, всего: 29". Это плохой
вариант. А мой лучший вариант покажу потом, если никто его не обгонит.
bye
Boris Sivko
Monday September 24 2007 23:32, Dmitry Grebeniuk wrote to All:
DG> Дан язык C. Hаписать функцию, принимающую один аргумент, являющийся
DG> восьмибитным числом (либо 8-битный тип, либо больше, но ненулевыми
DG> могут быть только младшие 8 бит), и возвращающую 0, не аргумент
DG> делится на 3, и "не 0" если делится. При этом разрешено использовать
DG> только такие операции: сложение, битовые сдвиги, логические and, or,
DG> битовые and, or, xor и целочисленные сравнения, и только такие
DG> возможности языка, как определение локальных переменных, чтение
DG> аргумента и переменных, модификация переменных, возврат значения из
DG> функции. (конечно, среди доступных операций нет ни деления, ни взятия
DG> остатка, а среди возможностей языка нет возможности подсмотреть в
DG> табличку, иначе было бы не комуфло)
DG> Пиписькомерка -- количество и вид операций. Hапример, мой самый
DG> первый вариант имел такие характеристики: "сдвиги: 7, сложения: 8,
DG> битовые and: 8, битовые xor: 1, логические or: 2, сравнения: 3, всего:
DG> 29". Это плохой вариант. А мой лучший вариант покажу потом, если
DG> никто его не обгонит.
Hавскидку так:
#include <iostream>
bool
func(char byte) {
char s = (byte & 15) + ((byte >> 4) & 15); // 7
s = (s & 3) + (s >> 2); // 4
if (s == 0) return true; // 4
if (s == 3) return true;
if (s == 6) return true;
if (s == 9) return true;
return false;
}
int main(int argc, char* argv[])
{
for( int i = 0; i < 256; ++i)
if (func(i) != (( i % 3 ) == 0))
std::cout << i << std::endl;
return 0;
}
─ ──── ─────── ─────────<конец цитаты>───────── ─────── ──── ─
Тут 7+4+4 = 15 операций. 6 сдвигов, 2 сложения, 3 побитных and, 4 сравнения.
Best regards,
Boris. e-mail: minx bk ru, ICQ: 2040111
Dmitry Grebeniuk
BS> if (s == 0) return true; // 4
BS> if (s == 3) return true;
BS> if (s == 6) return true;
BS> if (s == 9) return true;
BS> Тут 7+4+4 = 15 операций. 6 сдвигов, 2 сложения, 3 побитных and, 4
BS> сравнения.
Весьма неплохо "навскидку" получилось. Hо if'ы не разрешены, поэтому добавим
3 логических or (более оптимального ничего не вижу), то есть, кончик перепишем
как "return (s==0 || s==3 || s==6 || s==9)", что даст 18 операций.
Hо есть варианты лучше :)
bye
Dmitry Grebeniuk
BS> char s = (byte & 15) + ((byte >> 4) & 15); // 7
BS> s = (s & 3) + (s >> 2); // 4
BS> if (s == 0) return true; // 4
BS> if (s == 3) return true;
BS> if (s == 6) return true;
BS> if (s == 9) return true;
BS> Тут 7+4+4 = 15 операций. 6 сдвигов, 2 сложения, 3 побитных and, 4
BS> сравнения.
Тьфу. Чего клевещете на себя... _2_ сдвига, 2 сложения, 3 побитных and, 4
сравнения, ну и плюс 3 логических or. Итого 14 операций. Тем не менее, есть
лучше.
bye
Michael Mamaev
Втоpник Сентябpь 25 2007 21:41, Dmitry Grebeniuk wrote to Boris Sivko:
DG> Тьфy. Чего клевещете на себя... _2_ сдвига, 2 сложения, 3 побитных
DG> and, 4 сpавнения, нy и плюс 3 логических or. Итого 14 опеpаций. Тем
DG> не менее, есть лyчше.
11:
int func(unsigned int x)
{
unsigned int t = x + 2;
t += t >> 4;
t += t >> 2;
t -= t >> 1;
t >>= 1;
return t + t + t == x;
}
Если еще подyмать, может быть полyчится избавиться от +2 и yмножение на тpи
как-нибyдь покpасивее записать...
Майкл
Dmitry Grebeniuk
MM> t -= t >> 1;
MM> Если еще подyмать, может быть полyчится избавиться от +2 и yмножение
MM> на тpи как-нибyдь покpасивее записать...
Хехе, минус нельзя :)
bye
Michael Mamaev
Воскpесенье Сентябpь 30 2007 16:01, Dmitry Grebeniuk wrote to Michael Mamaev:
MM>> t -= t >> 1;
DG> Хехе, минyс нельзя :)
а) вы батенька совсем извpащенец :)
б) я yже видимо совсем засыпал вчеpа когда это делал, вот так очевидно бyдет то
же самое и еще быстpее:
int func(unsigned int x)
{
unsigned int t = x + 2;
t += t >> 4;
t += t >> 2;
t >>= 2;
return t + t + t == x;
}
Майкл
Boris Sivko
Sunday September 30 2007 16:01, Dmitry Grebeniuk wrote to Michael Mamaev:
MM>> t -= t >> 1;
MM>> Если еще подyмать, может быть полyчится избавиться от +2 и
MM>> yмножение на тpи как-нибyдь покpасивее записать...
DG> Хехе, минус нельзя :)
Какое-то странное там у тебя АЛУ. Судя по первычному описанию подумал, что
это что-то типа i8086. А тут получается что сдвигать умеет на произвольное
число
бит, а вычитать не умеет..
Boris Sivko
Tuesday September 25 2007 21:31, Dmitry Grebeniuk wrote to Boris Sivko:
DG> Весьма неплохо "навскидку" получилось. Hо if'ы не разрешены,
DG> поэтому добавим 3 логических or (более оптимального ничего не вижу),
DG> то есть, кончик перепишем как "return (s==0 || s==3 || s==6 || s==9)",
DG> что даст 18 операций.
DG> Hо есть варианты лучше :)
Hавскидку потому что особо не думал. Тут взглянул и нашел сразу ещё -2
операции(итого 12):
char s = (byte & 15) + (byte >> 4);
s = (s & 3) + (s >> 2);
s = (s & 3) + (s >> 2);
return (s == 0)||(s == 3);
Кроме того по условию вызов функции бесплатный. Откуда:
unsigned char
f2(const unsigned char & s) {
return ((s & 3) + (s >> 2));
}
bool
func(unsigned char byte) {
unsigned char s = f2(f2(f2(f2(byte)))); // 3
return (s == 0)||(s == 3); // 3
}
6 операций.
Dmitry Grebeniuk
DG>> Хехе, минус нельзя :)
BS> Какое-то странное там у тебя АЛУ. Судя по первычному описанию
BS> подумал, что это что-то типа i8086. А тут получается что сдвигать
BS> умеет на произвольное число бит, а вычитать не умеет..
Что-то мне кажется, что в i8086 таки были умножения и деления.
А если бы это было у меня, там было бы (x%3)==0 :)
Это просто задачка такая извращённая. Как мне она попала, так я её
опубликовал.
bye
Dmitry Grebeniuk
BS> Hавскидку потому что особо не думал. Тут взглянул и нашел сразу ещё
BS> -2 операции(итого 12):
Решение принято (однако разберу его чуть попозже).
BS> Кроме того по условию вызов функции бесплатный. Откуда:
По условию вызовов функций нет вообще :) Иначе было бы всё слишком просто.
Однако решение выглядит прилично, его тоже буду разбирать.
bye