задачка: делимость на три

[Dmitry Grebeniuk]

hi, All

Мне подкинули задачку. Категория "битовый онанизм". Практической ценности
почти не имеет, разве что моск размять.
Дан язык 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]

Hello Dmitry!

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]

hi, Boris

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

[Boris Sivko]

Hello Dmitry!

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 операций.

Best regards,
Boris. e-mail: minx bk ru, ICQ: 2040111

[Dmitry Grebeniuk]

hi, Boris

BS> Hавскидку потому что особо не думал. Тут взглянул и нашел сразу ещё
BS> -2 операции(итого 12):

Решение принято (однако разберу его чуть попозже).

BS> Кроме того по условию вызов функции бесплатный. Откуда:

По условию вызовов функций нет вообще :) Иначе было бы всё слишком просто.
Однако решение выглядит прилично, его тоже буду разбирать.

bye

[Dmitry Grebeniuk]

hi, Boris

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азyмy ждyт Вас в далеких миpах, Dmitry...
Вто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]

hi, Michael

MM> t -= t >> 1;

MM> Если еще подyмать, может быть полyчится избавиться от +2 и yмножение
MM> на тpи как-нибyдь покpасивее записать...

Хехе, минус нельзя :)

bye

[Michael Mamaev]

Хайль Гитлеp капyт, Dmitry!
Воск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]

Hello Dmitry!

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

Best regards,
Boris. e-mail: minx bk ru, ICQ: 2040111

[Dmitry Grebeniuk]

hi, Boris

DG>> Хехе, минус нельзя :)

BS> Какое-то странное там у тебя АЛУ. Судя по первычному описанию
BS> подумал, что это что-то типа i8086. А тут получается что сдвигать
BS> умеет на произвольное число бит, а вычитать не умеет..

Что-то мне кажется, что в i8086 таки были умножения и деления.
А если бы это было у меня, там было бы (x%3)==0 :)
Это просто задачка такая извращённая. Как мне она попала, так я её
опубликовал.

bye