определить как часто в массиве данных присутствует заданный бит

Question

Подскажите, есть ли какое-то безусловное (без использования условий) решение следующей задаче:

Есть массив 32битных чисел. Требуется на выходе получить 32битное число, где если i-ый бит установлен, то это означает, что i-ый бит в массиве данных встречается 2 раза, в противном случае i-ый бит сброшен

Т.е. к примеру

0b1011
0b1001
0b0010
0b1100
------
0b0011

понятно, что задачу можно решить создав массив из 32 элементов и когда бит в элементе массива установлен - увеличивать значение соответствующей ячейки массива

arr[32] = {0};
for (const int value : data)
{
    for (int index = 0; index < 32; index ++)
    {
        if (value & (1 << index))
            arr[index] ++;
    }
}

int res = 0;
for (int index = 0; index < 32; index ++)
    res |= arr[index] == 2 ? (1 << index) : 0;

но есть ли способ обойтись без этого if и вообще цикла по битам

частично конечно можно сделать так:

    for (int index = 0; index < 32; index ++)
        arr[index] += (value & (1 << index)) >> index;

но это полумера

Answer 1

Придумал быстрый алгоритм.

Для N чисел будет 3 * N итераций, всего 9 * N битовых операций не считая итерирования переменной цикла. Причём ровно столько же операций будет и для 64-битных чисел (на 64-битном процессоре) вместо 32-битных чисел, если надо расширить задачу до 64-битных чисел (поменять строку using WordT ...).

После прохода первых k чисел cnt[i] хранит u32 такой что j-й бит у него равен 1 тогда и только тогда когда в этих первых k числах j-й бит встретился ровно i раз. j-й бит всегда установлен ровно в одном из cnt[i] (0 <= i < 4).

Если в очередном числе j-й бит равен 1 и при этом также в неком cnt[i] также j-й бит равен 1, то этот единичный бит переходит в j-й бит в cnt[i + 1], а j-й бит cnt[i] зануляется, такой операцией мы увеличиваем на 1 подсчитанное число единиц в j-й позиции.

Массив cnt всегда содержит ровно 4 элемента для нашей задачи, не зависимо от N. В начале cnt[0] содержит все единичные биты, а остальные cnt[i] (1 <= i < 4) равны нулю.

В конце ответом будет cnt[2].

Для дальнейшего ускорения (оптимизации) можно внутренний цикл развернуть (unroll), хотя современные компиляторы итак это часто делают, там всего ровно 3 итерации у него всегда. Можно даже cnt массив заменить на несколько переменных типа uint32_t.

Попробовать код онлайн!

#include <vector>
#include <cstdint>
#include <iostream>
#include <bitset>
#include <array>

using WordT = uint32_t;

int main() {
    // ns содержит входные числа, любое число элементов.
    std::vector<WordT> ns = {0b1011, 0b1001, 0b0010, 0b1100};
    // cnt всегда содержит ровно 4 элемента.
    std::array<WordT, 4> cnt = {~WordT(0), 0, 0, 0};
    for (auto n: ns) {
        for (ptrdiff_t i = cnt.size() - 1; i >= 0; --i) {
            auto m = cnt[i] & n;
            cnt[i] ^= m;
            cnt[i + 1] |= m;
        }
    }
    // ответ всегда будет в cnt[2]
    std::cout << "0b" << std::bitset<sizeof(WordT) * 8>(cnt[2]) << std::endl;
}

Вывод:

0b00000000000000000000000000000011

Также можно заметить что на самом деле операция cnt[i] ^= m; лишняя и не нужна, если финальный ответ взять как cnt[2] & ~cnt[3], в итоге получаем сокращённый (и ускоренный) алгоритм из 6 * N битовых операций:

Попробовать код онлайн!

#include <vector>
#include <cstdint>
#include <iostream>
#include <bitset>
#include <array>

using WordT = uint32_t;

int main() {
    // ns содержит входные числа, любое число элементов.
    std::vector<WordT> ns = {0b1011, 0b1001, 0b0010, 0b1100};
    // cnt всегда содержит ровно 4 элемента.
    std::array<WordT, 4> cnt = {~WordT(0), 0, 0, 0};
    for (auto n: ns)
        for (ptrdiff_t i = cnt.size() - 1; i >= 0; --i)
            cnt[i + 1] |= cnt[i] & n;
    std::cout << "0b" << std::bitset<sizeof(WordT) * 8>(cnt[2] & ~cnt[3]) << std::endl;
}

Answer 2

Совсем без if-ов не получилось (используется тернарный оператор при получении итогового значения)

#include <array>
#include <bitset>
#include <iostream>

const std::array<unsigned int, 32> masks = {
    0b00000000000000000000000000000001, 0b00000000000000000000000000000010,
    0b00000000000000000000000000000100, 0b00000000000000000000000000001000,
    0b00000000000000000000000000010000, 0b00000000000000000000000000100000,
    0b00000000000000000000000001000000, 0b00000000000000000000000010000000,
    0b00000000000000000000000100000000, 0b00000000000000000000001000000000,
    0b00000000000000000000010000000000, 0b00000000000000000000100000000000,
    0b00000000000000000001000000000000, 0b00000000000000000010000000000000,
    0b00000000000000000100000000000000, 0b00000000000000001000000000000000,
    0b00000000000000010000000000000000, 0b00000000000000100000000000000000,
    0b00000000000001000000000000000000, 0b00000000000010000000000000000000,
    0b00000000000100000000000000000000, 0b00000000001000000000000000000000,
    0b00000000010000000000000000000000, 0b00000000100000000000000000000000,
    0b00000001000000000000000000000000, 0b00000010000000000000000000000000,
    0b00000100000000000000000000000000, 0b00001000000000000000000000000000,
    0b00010000000000000000000000000000, 0b00100000000000000000000000000000,
    0b01000000000000000000000000000000, 0b10000000000000000000000000000000,
};

int main() {
  std::array<size_t, 32> rezults{};

  // clang-format off
  std::array<int, 5> input{
      0b00000000000000000001000000000001,
      0b01000000000000000010000000000000,
      0b00000000001000000010000000000000,
      0b00000000010000000001000000000000,
      0b01000000000000000011000000000001,
  };
  // clang-format on

  for (size_t val : input) {
    for (size_t index = 0; index < masks.size(); ++index) {
      rezults[index] += val & masks[index];
    }
  }

  unsigned int response = 0;
  for (size_t index = 0; index < masks.size(); ++index) {
    unsigned int mask = masks[index];
    unsigned int val = rezults[index] >> 1;

    response |= val == mask ? mask : 0;
  }

  std::cout << "0b" << std::bitset<32>(response) << std::endl;

  return 0;
}

Answer 3

unsigned int a = 0, b = 0;
unsigned int x[5] = { 1, 3, 5, 4, 8 }; // Ну, сколько надо :)

// Магический цикл :)
for(int i = 0; i < 5; ++i)
{
    unsigned int s = a;
    a = a|(b&x[i]);
    b = (b&~x[i])|(~s&x[i]);
}
// Получение нужного результата
unsigned int z = a&b;

Ну, как вариант -

unsigned int step(unsigned int x, unsigned int &a, unsigned int&b)
{
    unsigned int s = a;
    a = a|(b&x);
    b = (b&~x)|(~s&x);
    return a&b;
}

Изначально a и b должны быть нулями; они хранят текущее состояние. Меньше, чем два бита на состояние, обойтись не получится. После каждого нового x функция возвращает искомое число. Его же можно в любой момент получить как a&b.

Логику конечного автомата пояснять надо или она очевидна?

Answer 4

пришла в голову следующая логика:

как получить 2

установить бит в переменной 1 (т.е. бит встречался хотя бы 1 раз)
установить бит в переменной 2, если бит в переменной 1 уже был установлен (т.е. бит встречался хотя бы 2 раза)
установить бит в переменной 3, если бит в переменной 2 уже был установлен (т.е. бит встречался хотя бы 3 раза)

правда порядок 3 - 2 - 1 должен быть

в итоге в конце в переменных 1 и 2 биты должны быть установлены, а в переменной 3 - нет - это и будет показатель того, что было всего 2 бита в данных

int bits1 = 0;
int bits2 = 0;
int bits3 = 0;

for (const int value : data)
{
    bits3 |= bits2 & value;
    bits2 |= bits1 & value;
    bits1 |= value;
}

const int res = bits1 & bits2 & (~bits3);

что скажете?

БЛОГ НА HUSL

определить как часто в массиве данных присутствует заданный бит

Ответы (4 шт):