подсчёт количества разных элементов в массиве

[koky]

Вот пример из одного пособия. Очень непонятный:
Вариант 3. Использование логической шкалы для подсчета количества разных элементов в целочисленном массиве с положительными данными. Если массив содержит отрицательные элементы, то при первом проходе можно определить максимальный из них и на эту величину сместить все значения. Идея использования логической шкалы состоит в том, что с каждым двоичным разрядом шкалы можно связать последовательно возрастающие целые числа. Сначала все биты логической шкалы сбрасываются в 0. Затем организуется цикл просмотра всех элементов массива, при котором мы определяем номер разряда в шкале, соответствующий проверяемому значению. Если в соответствующей позиции шкалы находится 0, то такое число встретилось впервые и к счетчику разных чисел надо добавить 1. В противном случае такое число уже попадалось и его надо пропустить.
Обратите внимание на следующие приемы работы со шкалой. Во-первых, под нее надо запросить память (желательно, чистую). Это можно сделать следующим образом. Если длина нашего массива не превышает 32767 элементов, то под логическую шкалу потребуется не более 4096 байт. Запрос памяти под шкалу лучше всего организовать через библиотечную функцию calloc. У нее задается два аргумента – количество элементов данных и число байт, необходимых для хранения каждого элемента:
b=calloc(4096,1); //запрос чистой памяти
Во вторых, для перевода целого числа N в соответствующий разряд шкалы b удобнее воспользоваться номером байта шкала (переменная byte) и номером бита (переменная bit) в этом байте. Кроме этого нам потребуется массив из 8 однобайтовых констант, каждая из которых представляет один бит шкалы:
char mask[8]={128,64,32,16,8,4,2,1};
Для определения номеров байта и бита, соответствующих числу N, достаточно проделать два деления:
byte=N / 8;
bit =N % 8;
В итоге окончательный вид функции difference таков:
int difference(int *a,int n)
{ int bit,byte,i,m=0;
char mask[8]={128,64,32,16,8,4,2,1};
char *b=(char *)calloc(4096,1); //запрос и очистка памяти
for(i=0; i<n; i++)
{ byte = a[i] / 8;
bit = a[i] % 8;
if((b[byte]& mask[bit])==0) //проверка бита шкалы
{ m++; b[byte] |= mask[bit]; } //вписывание бита в шкалу
}
free(b); //освобождение памяти
return m;
}
При окончательной сборке программы надо не забыть подключить заголовочный файл alloc.h, в котором находится прототип функции calloc.


непонятно почти всё.. "Если длина нашего массива не превышает 32767 элементов, то под логическую шкалу потребуется не более 4096 байт" - вот это например..в смысле 32767 элементов? а каждый элемент это бит что ли?... да вроде нет.. потом это" if((b[byte]& mask[bit])==0) //проверка бита шкалы"
а mask[bit] как может быть равен 0..вобщем всё непонятно..может ли кто-нибудь пояснить этот код более нормально?

[Pavia]

Да бит.
У нас есть массив бит. Каждому биту присвоен порядковый номер. Если бит стоит, то он означает что число равное порядковому номеру бита есть в множестве.
Если бит сброшен, то такого числа нет в множестве. Вот проверяем бит и если он 0 то увеличиваем.

Цитата:

а mask[bit] как может быть равен 0.

А мы не его проверяем, а бит из b[byte].

8 битами мы можем закодировать множество из 8 чисел {0,1,2,3,4,5,6,7}.
0 1 2 3 4 5 6 7 - числа
0 0 0 0 0 0 0 0 {} - пустое множество
1 0 0 0 0 0 0 0 {0}
1 0 1 0 0 0 0 0 {0,2}
0 1 0 1 0 0 0 0 {1,3}
1 1 1 1 0 0 0 0 {0,1,2,3}

А так как в байте 8 бит то. Одним байтом можно закодировать множество из 8 чисел.
4096 байт соответственно кодируют множесто из 4096*8 чисел.