Здравствуйте, NickName, Вы писали:

NN>Мне рассказывали задачку, которая предлогалась на приеме в израильское отделение Intel. Итак:

NN>Вождь племени говорит индейцам:
NN>- Ваши жёны (как минимум одна) изменяют вам. Если вы ловите супругу на измене — убивайте её.
NN>Две ночи в деревне было тихо, после чего раздались выстрелы:
NN>Вопрос: Что происходило в эти две ночи?

NN>Имеется в виду, как рассуждал какой-нить индеец?
Такую задачку испортили... она изначально была многим сложнее и интереснее...

Здравствуйте, Anatoliy Elsukov, Вы писали:

AE>Здравствуйте, NickName, Вы писали:

AE>Такую задачку испортили... она изначально была многим сложнее и интереснее...
Если Вас не затруднит, приведите Ваш вариант... Было бы неплохо, если с решением

Написать функцию, подсчитывающую количество битов в двойном слове.
Оптимально причем

КАА>Написать функцию, подсчитывающую количество битов в двойном слове.
КАА>Оптимально причем

Оптимально по скорости? Табличку забацать, в 256, а еще более оптимально — в 65536 значений.

Здравствуйте, Igor Trofimov, Вы писали:

КАА>>Написать функцию, подсчитывающую количество битов в двойном слове.
КАА>>Оптимально причем

IT>Оптимально по скорости? Табличку забацать, в 256, а еще более оптимально — в 65536 значений.

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

Здравствуйте, КАА, Вы писали:

КАА>Написать функцию, подсчитывающую количество битов в двойном слове.
КАА>Оптимально причем
Сразу оговорюсь придумал не я

unsigned int bitcount(unsigned int n) 
{
    n = (n&0x55555555) + ((n >> 1)&0x55555555);
    n = (n&0x33333333) + ((n >> 2)&0x33333333);
    n = (n&0x0F0F0F0F) + ((n >> 4)&0x0F0F0F0F);
    n = (n&0x00FF00FF) + ((n >> 8)&0x00FF00FF);
    n = n + (n >> 16);
    return n;
}

Да уж, баги неистребимы

...
    return n&0xFF;
}

Сламин, спасибо большое за столь интересную функцию

Думаю моим студентам она понравится . В качестве разминки перед след. лабой :D).

Этот способ хоть немного уступает в скорости табличному, лично мне нравится много больше . Уж больно изящен .

Здравствуйте, Anton V. Kolotaev, Вы писали:

AV>Здравствуйте, Igor Trofimov, Вы писали:

КАА>>>Написать функцию, подсчитывающую количество битов в двойном слове.
КАА>>>Оптимально причем

IT>>Оптимально по скорости? Табличку забацать, в 256, а еще более оптимально — в 65536 значений.

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

Небольшое усложнение ситуации. Пусть кэш у нас имеет нестандартный размер. 200 байт. Как тут поступить?

Здравствуйте, zaiats_2k, Вы писали:

A>>Когда холодильник не открыт он нагревает комнату.

Z2>Когда открыт — тоже нагревает.

Z2>Вот мы и выяснили что такое холодильник — изощрённый нагревательный прибор.

Да так и есть, если мне память не изменяет из школьного курса физики. Там была формула КПД, которая гласит, что у холодильника, он очень низкий. Соответственно, это значит, что он совершенный нагреватель.

Здравствуйте, КАА, Вы писали:

КАА>Написать функцию, подсчитывающую количество битов в двойном слове.
КАА>Оптимально причем

наверное так:

size_t get_dword_bits_count()
{
    return 8*sizeof(DWORD);
}

Абсолютно оптимально! По идее все должно посчитаться на этапе компиляции.

Hello, Atilla!
You wrote on Sun, 22 Dec 2002 17:48:57 GMT:
A> From: Atilla Оценить
A> Здравствуйте, КАА, Вы писали:
КАА>> Написать функцию, подсчитывающую количество битов в двойном слове.
КАА>> Оптимально причем
A> наверное так:
A> size_t get_dword_bits_count()
A> {
A> return 8*sizeof(DWORD);
A> }
A> Абсолютно оптимально! По идее все должно посчитаться на этапе
A> компиляции.
A> ... << RSDN@Home 1.0 beta 3 >>
наконец-то первое здравое решение из области "какой вопрос — такой ответ"!!
но вышеприведенное решение с подсчетом выставленных бит все равно супер,
чего не отнять, того не отнять!
With best regards, Valery A. Boronin. E-mail: boronin@novosoft.ru

Здравствуйте, КАА, Вы писали:

КАА>Написать функцию, подсчитывающую количество битов в двойном слове.
КАА>Оптимально причем

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

unsigned int bits(unsigned int x)
{
  if(x == 0) return 0;

  unsigned int c = 1;
  while((x &= x-1) != 0) c++;

  return c;
}

Здравствуйте, Аноним, Вы писали:

А>расскажите кто какие задачки решал на собеседованиях при приеме на работу.

Я правда туда не собеседовался
Но, говорят, Микрософт даёт и такую вот задачку:

На прямоугольном листе бумаги нарисован (как попало) прямоугольник.
Перегибами надо разделить область ВНЕ прямоугольника пополам.

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Аноним, Вы писали:

А>>расскажите кто какие задачки решал на собеседованиях при приеме на работу.

P>Я правда туда не собеседовался
P>Но, говорят, Микрософт даёт и такую вот задачку:

P>На прямоугольном листе бумаги нарисован (как попало) прямоугольник.
P>Перегибами надо разделить область ВНЕ прямоугольника пополам.

Что значит "пополам?".
это понятией растежимое

По оптимальности это существенно медленнее... существенно.
Да и насчет красоты — спорный момент.

Действительно обалденный метод показал Slamin.

Здравствуйте, Slamin, Вы писали:

>Здравствуйте, КАА, Вы писали:

КАА>>Написать функцию, подсчитывающую количество битов в двойном слове.
КАА>>Оптимально причем

> unsigned int bitcount(unsigned int n) {...}

Уважаемые господа специалисты. Бесспорно, красиво. Наверное оптимально.
Одно обидно — непонятно. Сказано: хочешь понять всю глубину предмета — объясни дураку.
Объясните, пожалуйста, на чём основан этот алгоритм? В чём идея?

Премного благодарен.

Вот тут есть кое-какое объяснение
http://www.sdteam.com/algoritms/bits.html

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Аноним, Вы писали:

А>>расскажите кто какие задачки решал на собеседованиях при приеме на работу.

P>Я правда туда не собеседовался
P>Но, говорят, Микрософт даёт и такую вот задачку:

P>На прямоугольном листе бумаги нарисован (как попало) прямоугольник.
P>Перегибами надо разделить область ВНЕ прямоугольника пополам.

Прочертить линию через две точки — центры двух прямоугольников. Прямоугольники: весь лист бумаги и тот самый, малый, нарисованный "как попало" прямоугольник. Центром прямоугольника считать точку пересечения его диагоналей.
Прочерченная таким образом линия будет делить как площадь листа бумаги пополам, так и площадь малого прямоугольника. А стало быть вся оставшаяся площадь ВНЕ прямоугольника тоже делиться пополам.
Дальше можно легко разделить бумагу "перегибами" вдоль этой линии и контура малого прямоугольника. Это оставлю на любителей "побаловаться с бумагой" .

Здравствуйте, Аноним, Вы писали:

А>Прочертить линию через две точки — центры двух прямоугольников. Прямоугольники: весь лист бумаги и тот самый, малый, нарисованный "как попало" прямоугольник. Центром прямоугольника считать точку пересечения его диагоналей.
А>Прочерченная таким образом линия будет делить как площадь листа бумаги пополам, так и площадь малого прямоугольника. А стало быть вся оставшаяся площадь ВНЕ прямоугольника тоже делиться пополам.
А>Дальше можно легко разделить бумагу "перегибами" вдоль этой линии и контура малого прямоугольника. Это оставлю на любителей "побаловаться с бумагой" .

Жаль что ты аноним, а то бы 15 баллов заработал.