Срочно! Помогите с алгоритмом
 

Необходимо написать функцию на С++ которая вернет количество нулевых бит в символах строки, не считая символ конца строки. Написать 2 способами - быстрым и обычным.

Проблема в том что с С++ не знаком, только начал изучать а задача есть. Помогите плиз!!

Re: Срочно! Помогите с алгоритмом
 

Всем спасибо!! Написал сам!!

/*Slow method*/
int CountZeroBits(const char* Str)
{
int Result = 0;
for (int i = 0; i < StrLen(Str); i++)
for (int j = 0; j <= 7; j++)
if (Str[i] & (1 << j) == 0) Result += 1;
return Result;
}

//fast method
int CountZeroBits(const char* Str)
{
const
byte CountBitsInTetra[16] =
{4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
for (int i = 0; i < StrLen(Str); i++)
Result += CountBitsInTetra[Str[i] & 15] + CountBitsInTetra[Str[i] >> 4];
return Result;
}

Re: Срочно! Помогите с алгоритмом
 

а что означает массив byte CountBitsInTetra[16] =
{4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0}; ?
откуда цифры?

Re: Срочно! Помогите с алгоритмом
 

Я бы StrLen(Str) вынес из цикла ИМХО быстрее работать будет, если 4 байта памяти под инт не жалко

Re: Срочно! Помогите с алгоритмом
 

почему быстрее ?

Re: Срочно! Помогите с алгоритмом
 

так он уже сам написал :)

Re: Срочно! Помогите с алгоритмом
 

Так все-таки - почему быстрее? У самого есть подобное решение и не прочь его оптимизировать.

Re: Срочно! Помогите с алгоритмом
 

В качестве второго варианта, более быстрого, но требующего больше памяти могу предложить:
вместо:
for (int j = 0; j <= 7; j++)
if (Str[i] & (1 << j) == 0) Result += 1;
return Result;
создаём массив из 256 чисел, каждое из которых соответствует число нулей в соответствующем числе.
Например,
unsigned char ZeroAmount [] = { 8, 7, 7, 6, 7, 6, 6, 5, ... и так далее. }

Добавлено через 3 минуты
Тогда число нулевых битов в каждом символе строки будет ZeroAmount[Str[i]]