Nano Hash - криптовалюты, майнинг, программирование

Как реализовать битовые векторы с побитовыми операциями?

Я изучаю вопрос в книге Programming Pearls, и они рекомендовали эту функцию, чтобы установить бит в битовом векторе. Я немного смущен тем, что он делает.

#define BITSPERWORD 32
#define MASK 0x1F
#define SHIFT 5
#define N 1000000

int a[1 + N/BITSPERWORD];

void set(int i){
   a[i >> SHIFT] |= (1 << (i & MASK)); 
}

Вот моя (вероятно неправильная) интерпретация этого кода. если я = 64,

1) сначала он берет i и сдвигает его вправо на SHIFT (то есть 5) бит. Это эквивалентно ДЕЛЕНИЮ (а не умножению, как я сначала подумал) i на 2^5. Итак, если i равно 64, индекс a равен 2 (64 / 2^5)

2) a[2] |= (1 << (64 & MASK))
64 & 1 = 1000000 & 01 = 1000001.
Итак, 1 сдвигается влево на сколько бит????

c c++ bit-manipulation bitwise-operators
20.07.2013

  • Сдвиг вправо делит на два. 20.07.2013
  • This is equivalent to multiplying i by 2^5. НЕТ Это эквивалентно делению i на 2^5. 20.07.2013
  • Вы уверены, что i это int, а не unsigned int ? откуда вы взяли этот код? 20.07.2013
  • Упс. Итак, я изменил его, чтобы отразить деление на 2 ^ 5. Что насчет остальных? 20.07.2013
  • 2 (64 / 2^5) ? или только (64 / 2^5)... думаю, если 1000 >> 1 == 0100 так x >> 5 == x / 2^5 только 20.07.2013
  • Обратите внимание, что для реального кода вы можете вместо этого использовать std::bitset. Он уже реализует большую часть того, что вам может понадобиться (и, возможно, даже больше). 20.07.2013
  • @ Хенли Чиу Вот подарок для вас. 20.07.2013
  • если i == 64, то должно быть 64 и MASK = 0 20.07.2013
  • @aaronman хорошо, но поскольку ты ответил Хенли, так что все в порядке. 20.07.2013
  • @GrjeshChauhan, если вы отвечаете на удаленный комментарий, я действительно сделал ошибку 20.07.2013

Ответы:


1
  1. Кажется, как этот метод работает, хотя я чувствую, что есть лучшие способы установить немного. Чтобы найти индекс бита ith, он по существу делится на 32, потому что это количество битов в слове.
  2. Поскольку здесь используется оператор |, функция устанавливает бит в единицу, не переключая бит
  3. 0x1F на самом деле 31, и при объединении с i вы получаете остаток (не знаю, почему они просто не использовали %)
  4. И, наконец, сдвиг переносит 1 в нужное место и или в правильный слот в векторе.

Если вы планируете использовать этот код

  1. вы могли бы написать это очень ясно без определений и с использованием более очевидных методов, я сомневаюсь, что это повлияет на скорость.
  2. Также вам, вероятно, следует просто использовать std::bitset
  3. использование маски для получения остатка особенно раздражало меня, потому что я почти уверен, что это не обязательно будет работать для каждого числа, 31 работает, потому что это все 1
20.07.2013
  • +1 за уточнение 0X1F - 31. Я все время думал, что это 1. УХ ТЫ. Это многое проясняет. Спасибо. 20.07.2013
  • @HenleyChiu, лол, нет проблем, честно говоря, есть гораздо более понятные способы установить бит, мне не нравится этот код 20.07.2013
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..