"Искусство программирования" (задача 3)

[vimmax]

Написать подпрограмму, вычисляющую количество единиц в бинарном представлении целого числа, например в числе 6 две единицы (6 = 0110_bin), в числе 7 три единицы (7 = 0111_bin).

Условия:
Реализацию этого алгоритма можно предложить на любом языке программирования. Мой
ответ на ANSI С.

Будет защитан только самый быстрый алгоритм, т.е. подпрограмма должна быть оптимизирована по времени.

[BODROV]

     mov bx, x
     mov ax, 0
     mov cx, 16
m: rcl bx, 1
     adc ax, 0
     loop m

в результате в ax кол-во единиц. но что-то мне подсказыавет, что это не самый лучший вариат....

[vimmax]

BODROV - Ответ #1 - вау, скока программистов на асме нашлось!!!!
Ответ хороший, но не самый быстрый. Фишка данной задачи в том, что ответ можно реализовать на любом языке программирования. Хотя ответ немного абсурдный.....но самый быстрый.

[Archangel]

Ставишь мультиплексоры, а после них счетчики:). Работать будет быстрее всего остального.

[vimmax]

Archangel - Ответ #3 - Может быть и быстрее, но сейчас тема "Искусство программирования", а не "Искусство схемотехники" )))

[vimmax]

Такс,....ну что товарисчи ?? Даже никто и не пытается? В общем даю подсказку:
Оптимизация программ обычно ведется в одном из двух направлений: 1.оптимизация по скорости с увеличением занимаемой памяти 2.оптимизация по занимаемой памяти в ущерб скорости.

В данной задаче время выполнения алгоритма уменьшается за увеличения занимаемой памяти...

[BODROV]

создать массив скажем из 65535 элементов, где заведомо указать в i-том элементе количество единиц числа i   

[Sochin]

создать массив скажем из 65535 элементов, где заведомо указать в i-том элементе количество единиц числа i   

А для оптимизации по времени поиска элемента использовать хеш-таблицу или двоичное дерево.

[vimmax]

BODROV, Sochin - Все бы хорошо, но приведите пример кода, можно без компиляции и без лишних элементов. Хоть пару строк....

[BODROV]

const
  a: array [0..65535] of integer = (0,1,1,2,1,2,2,3,1,2 ...и так далее... 16);
var
  z: word;
begin
  readln(z);
  writeln('код-во единиц: ', a[z]);
end.

[vimmax]

BODROV - Ответ#9 - Правильный ответ, самый быстрый. Скорость в ущерб памяти     +1.

Sochin - Ответ #7 - интересно было-бы посмотреть реализацию с хеш-таблицами и бинарным деревом.

[BODROV]

BODROV - Ответ#9 - Правильный ответ, самый быстрый. Скорость в ущерб памяти     +1.

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

[Sochin]

Sochin - Ответ #7 - интересно было-бы посмотреть реализацию с хеш-таблицами и бинарным деревом.

Вот так с помощью хэша можно искать для целых или скажем для строк(C#):

Код:

    public class BitCounter
    {
        static BitCounter()
        {
            hash.Add(0, 0);
            hash.Add(1, 1);
            hash.Add(2, 1);
            hash.Add(3, 2);
            ...
            hash.Add(65535, 16);
            hash.Add("0", 0);
            hash.Add("1", 1);
            hash.Add("2", 1);
            hash.Add("3", 2);
            ...
            hash.Add("65535", 16);
        }

        static Hashtable hash = new Hashtable();

        public static int Count(object x)
        {
            if (hash.Contains(x)) return (int) hash[x];
            return 0;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Кол-во единиц: {0:D}", BitCounter.Count(3));
            Console.WriteLine("Кол-во единиц: {0:D}", BitCounter.Count("3"));
            Console.ReadLine();
        }
    }

Кстати насчет абсурдности идеи как таковой, индексы в СУБД MS SQL Server предназначены для ускорения поиска и представляют собой ничто иное как сбалансированные деревья.

[mars]

Ставишь мультиплексоры, а после них счетчики:). Работать будет быстрее всего остального.

Очень хотелось бы схемку с мультиплексором увидеть ....
хе-хе