Считайте единицы в BitVec в Z3 с форматом ввода Datalog

Существует ли компактный способ подсчета количества битов, для которых установлено значение 1 в BitVec в Z3, с использованием формата ввода Datalog?

$ z3 -h  # most of the lines below omited for clarity
Input format:
  -dl         use parser for Datalog input format.

Принятый в настоящее время ответ на этот вопрос: Считайте единицы в BitVec в Z3 с входным форматом SMT 2 говорится, что нет хорошего способа сделать это во входном формате SMT 2.

Принятый в настоящее время ответ на этот вопрос: Сумма все биты в битовом векторе Z3 показывает, как это сделать в Python.


z3 datalog
person km9c3uwc    schedule 04.07.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Для векторов 32 bit вы можете попытаться перевести следующий псевдокод в SMT:

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

Это называется Bit Twiddling Hack и также было опубликовано здесь.

person Axel Kemper    schedule 04.07.2018
comment
Спасибо! Это действительно интересная идея использовать этот хак, чтобы уменьшить количество шаблонного кода. (Тем не менее, этот вопрос касается формата ввода журнала данных.) - person km9c3uwc; 04.07.2018