Могу ли я проверить в C (++), является ли массив все 0 (или false)

Question

Могу ли я проверить в C (++), является ли массив равным 0 (или ложью), не повторяя / не повторяя каждое отдельное значение и не выделяя новый массив того же размера (для использования memcmp)?

Я злоупотребляю массивом bools, чтобы иметь произвольные большие наборы битов во время выполнения, и выполняю некоторые битовые перетаскивания на нем

Answer 1

Вы можете использовать следующее условие:

(myvector.end() == std::find(myvector.begin(), myvector.end(), true))

Очевидно, что внутренне это зацикливается на всех значениях.

Альтернатива (которая действительно должна избегать зацикливания) состоит в переопределении всех функций доступа к записи и отслеживании того, была ли когда-либо записана true в ваш вектор.

UPDATE

В комментариях Ли Райана ниже описан более надежный способ сделать это, основанный на том же принципе.

Answer 2

Если это не отсортировано, нет.Как бы вы планировали это сделать?Вам нужно будет проверить каждый элемент, чтобы увидеть, 0 это или нет!memcmp, конечно, также проверяет каждый элемент.Это было бы намного дороже, поскольку он также читает другой массив.

Конечно, вы можете заблаговременно, как только вы нажмете элемент, отличный от 0.

Ваш единственный вариант будетиспользовать SIMD (который технически все еще проверяет каждый элемент, но использует меньше инструкций), но вы обычно не делаете это в универсальном массиве.

(Кстати, мой ответ предполагает, что у вас есть простой статический C/ C ++ массив. Если вы можете указать, какой массив у вас есть, мы могли бы быть более конкретными.)

Answer 3

Предположим, что у вас есть массив из элемента N, вы можете выполнить битовую проверку по отношению к набору базовых векторов.

Например, у вас есть массив из 15 элементов, который вы хотите протестировать.

Вы можете проверить его на 8-элементном нулевом массиве, 4-элементном нулевом массиве, 2-элементном нулевом массиве и 1-элементном нулевом массиве.

Вы должны выделить эти элементы только один разучитывая, что вы знаете максимальный размер массивов, которые вы хотите проверить.Кроме того, тест может выполняться параллельно (и, если необходимо, с внутренней сборкой).

Дальнейшее улучшение срока выделения памяти может быть выполнено с использованием только 8-элементного массива, поскольку нулевой 4-элементный массивпросто первая половина 8-элементного нулевого массива.

Answer 4

Попробуйте использовать boost::dynamic_bitset.Он имеет none член и несколько других std::bitset -подобных операций, но его длина может быть установлена ​​во время выполнения.

Answer 5

Если вы знаете, что это будет требованием, вы можете построить структуру данных, состоящую из массива (возможно, динамического) и количества или в настоящее время ненулевых ячеек.Очевидно, что настройка ячеек должна быть абстрагирована, но это естественно в c ++ с перегрузкой, и вы можете использовать непрозрачный тип в c.

Answer 6

knittl,

Не думаю, что у вас есть доступ к некоторому причудливому оборудованию DMA на целевом компьютере?Иногда аппаратное обеспечение DMA поддерживает именно ту операцию, которая вам требуется, т. Е. «Является ли эта область памяти полностью нулевой?»Этот вид аппаратно-ускоренного сравнения является распространенным решением при работе с большими битовыми буферами.Например, некоторые RAID-контроллеры используют этот механизм для проверки на четность.

Answer 7

Вам не нужно перебирать всю вещь, просто прекратите зацикливание на первом ненулевом значении.

Я не могу придумать способ проверить набор значений, кроме проверки каждого из них по очереди - вы можете играть в игры с проверкой базовой памяти как нечто большее, чем bool (скажем, __int64)но выравнивание тогда является проблемой.

РЕДАКТИРОВАТЬ: Вы можете сохранить отдельное количество установленных битов и проверить, что это ненулевое значение.Вы должны быть осторожны с обслуживанием этого, чтобы установка бита не делала ++ этого и так далее.

Answer 8

Нет, вы можете сравнить массивы с memcmp, но вы не можете сравнить одно значение с блоком памяти.

То, что вы можете сделать, это использовать алгоритмы в C ++, но это все еще включает внутренний цикл.