Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Подсчет битов 
:(
    Опции темы
math64
Дата 18.3.2009, 17:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72
Есть массив из 256 битов
Код

unsigned char bits[32];

Нужно найти место в массиве где больше всего единичных битов.
Как это сделать оптимальнее?
PM   Вверх
Anikmar
Дата 18.3.2009, 17:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59
Больше всего что? Подряд?
PM MAIL ICQ   Вверх
zim22
Дата 18.3.2009, 17:23 (ссылка) | (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69
есть книга "Алгоритмические трюки для программистов". Генри Уоррен, мл.
она полностью посвящена битам. подсчёт, деление, перестановка и т.д.
возможно в ней будет ответ. smile



--------------------
C++ FAQ Lite
PM MAIL   Вверх
Alexeis
Дата 18.3.2009, 17:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 12
Всего: 459
Цитата(zim22 @  18.3.2009,  16:23 Найти цитируемый пост)
возможно в ней будет ответ.

  На 75й странице smile 


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
inside_pointer
Дата 18.3.2009, 22:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 344
Регистрация: 9.3.2008

Репутация: 5
Всего: 12
находишь точку 0xF, если нет находишь 0xE ну и т.д.
когда нашёл
делаешь то же самое для примыкающих слева и справа (слева для всех 1***, справа для всех ***1)
смахивает на бинарное дерево
PM MAIL   Вверх
math64
Дата 19.3.2009, 09:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72
Осносвной вариант алгоритма с стр. 75 я и так знал, но книга довольно интересная.
Нужно примерно это (неоптимально):
Код

unsigned char bits[32];
int w;

int getbit(int index) {
  index &= 0xFF;
  return (bits[index>>3] & (1 << (index&0x07))) == 0 ? 0 : 1;
}

int weight(int index) { return 1; }

int findmoreones() {
  int i, j, s, maxs, maxi;
  maxs = 0;
  maxi = 0;
  for(i=0; i < 256; i++) {
    s = getbit(i) * weight(0);
    if (s != 0) {
       for (j = 1; j <= w; j++) {
          s += getbit(i + j) * weight(j);
          s += getbit(i - j) * weight(j);
       }
       if (s >= maxs) {
         maxs = s;
         maxi = i;
       }
    }
  }
  return maxi;
}
PM   Вверх
azesmcar
Дата 19.3.2009, 09:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211
math64
Код

int nonZeroBitCount(unsigned char bits)
{
    int total = 0;    
    for (int i = 0; i < 8; ++i)
        total += (bits >> i) & 1;
    return total;
}


по моему так лучше

Добавлено через 8 минут и 1 секунду
Цитата

Есть массив из 256 битов


неверно понял вопрос...

Добавлено через 11 минут и 52 секунды
я не особо понял в таком случае..что значит больше всего? если подряд, тогда делай шифт вправо пока на ноль не наткнешся, как наткнешся обнуляй счетчик..не пойдет?

Это сообщение отредактировал(а) azesmcar - 19.3.2009, 09:38
PM   Вверх
math64
Дата 19.3.2009, 10:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72
Модем передаёт тестовое сообщение используя фазу = 0 ... 255. В результате получаем массив из 256 бит, 1 если сообщение успешно принято. Нужно определить какую фазу лучше использовать.
PM   Вверх
vinter
Дата 19.3.2009, 10:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Explorer
****


Профиль
Группа: Завсегдатай
Сообщений: 2735
Регистрация: 1.4.2006
Где: Н.Новгород

Репутация: 13
Всего: 56
а не проще использовать bitset\vector<bool>?


--------------------
Мой блог
PM MAIL WWW   Вверх
math64
Дата 19.3.2009, 12:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72
нет, всё будет работать на микропроцессоре с компилятором C без плюсов, желательно без умножения/деления и плавающей точки.

Вот алгоритмы из книги которые могут быть полезны:
Код

/* Подсчёт числа 1 битов в слове */
int pop (unsigned x)
{
  x = x - ( (x >> 1) & 0x55555555);
  x = (x & 0x33333333) + { (x >> 2) & 0x33333333);
  x = (х + (x >> 4)) & 0x0F0F0F0F;
  x = x + (x >> 8);
  x = x + (x >> 16);
  return х & 0х000000ЗF;
}

/* Подсчёт 0 битов права */
int ntz(unsigned x)
{
  return 32 - pop(x|-x);
}

/* поиск 8-ми 1 битов подряд */
int f8ones(unsigned x)
{
  x &= (x >> 1); // 1 где 2 бита подряд
  x &= (x >> 2); // 1 где 4 бита подряд
  x &= (x >> 4); // 1 где 8 бит подряд
  return ntz(x); // 32 если 8 бит подряд или номер бита
}
PM   Вверх
GoldFinch
Дата 19.3.2009, 12:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
чем писать на С такой изврат проще написать на асме этого МК, код выйдет компактнее и прозрачнее
PM MAIL ICQ   Вверх
azesmcar
Дата 19.3.2009, 12:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211
math64, я все еще не понимаю..что именно нужно подсчитать? найти место где больше всего 1 битов подряд???
PM   Вверх
zim22
Дата 19.3.2009, 13:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69
math64, простенький алгоритм придумал:
Код
// 490.cpp : Defines the entry point for the console application.
//
#include <iostream>

int main(int argc, char *argv[])
{
    unsigned char bits[32] = {0, 1, 2, 3, 4, 5, 6, 7, 255, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
    size_t cnt = 0, max_cnt = 0, pos = 0, max_pos = 0;
    for (size_t i = 0; i != sizeof(bits); ++i)
    {        
        for (size_t j = 0; j != 8; ++j)
            if (128>>j & bits[i]) { ++cnt; }
            else
            {
                pos = 8 * i + j;

                if (max_cnt < cnt)
                {
                    max_cnt = cnt;
                    max_pos = pos;
                }
                cnt = 0;
            }
    }
    std::cout << "Max number of bits: " <<  max_cnt << "\n" << "First position: " << max_pos - max_cnt << std::endl;

    return 0;
}




битовую последовательность я рассматриваю от старшего бита к младшему.



Это сообщение отредактировал(а) zim22 - 19.3.2009, 13:13


--------------------
C++ FAQ Lite
PM MAIL   Вверх
math64
Дата 19.3.2009, 13:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 8
Всего: 72
Нужно ещё добавить проверку что максимальная последовательность бит оказалась в конце массива
PM   Вверх
zim22
Дата 19.3.2009, 14:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


depict1
****


Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 24
Всего: 69
math64, перед строкой с cout добавьте
Код
if (max_cnt < cnt)
    {
        max_cnt = cnt;
        max_pos = pos + cnt;
    }




--------------------
C++ FAQ Lite
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1253 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.