подсчет положительных элементов в массиве без использования условного перехода

Question

Как я могу это сделать?

Я думаю, что я должен сделать что-то вроде вычисления контрольной суммы, но это должно дать число натуральных чисел в конечных битах.

edit: что, если мы не можем использовать 'shift', либо

edit2: ISA равен Y86

Answer 1

Поскольку я вижу, что вы очень обеспокоены производительностью: если вы можете кодировать на ассемблере, то для каждого элемента массива вы можете вычесть элемент из нуля (или сделать какой-то похожий трюк, который установит флаг переноса, если элемент было положительным), а затем выполнить инструкцию «АЦП» (или аналогичную) с нулевым операндом. ADC - это инструкция, которую предлагают почти все процессоры, и она означает «Добавить с переносом». Это добавит операнд плюс значение флага переноса ЦП в аккумулятор. Таким образом, если бы элемент был положительным, то вычитание из нуля установило бы флаг переноса, что означает, что аккумулятор будет увеличиваться; в противном случае флаг переноса будет сброшен, поэтому накопитель не будет увеличиваться. Я не думаю, что это может быть быстрее, чем это.

РЕДАКТИРОВАТЬ: о, и, неужели люди проголосуют за вопрос, пожалуйста, укажите, почему вы голосуете вниз? Потому что, понимаете, если нет, то получается, что такие люди, как я, вынуждены отменить ваше отрицательное голосование своим повышением.

Answer 2

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

Вы не указали язык, поэтому я буду использовать псевдокод, предполагая, что32-разрядные целые числа со знаком:

Set accumulator to 0
For each element in array
    sign = (element bitwise and 0x80000000) logical shift right by 31
    accumulator += sign
positive_count = length of array - accumulator

Answer 3

Если вы работаете с целочисленными типами, то гарантируется, что msb неотрицательного числа равно 0. ^* Так что все, что вам нужно сделать, это выделить msb каждого элемента массива по очереди.и накапливать.

---

_{* Это верно для дополнения до двух, дополнения до одного и величины знака.}