Генерирование желаемого числа побитовым ИЛИ

Ответ 1

Я предполагаю, что эта проблема является NP полной, хотя я не нашел NP трудную задачу, легко сводящуюся к этому.

Но для тех наборов, которые содержат 2 ^ (mostSignificantDigit) - 1, я бы сделал эвристику: во-первых, попробуйте число 1...1 (mostSignificantDigit-1), во-вторых, число с самым значительным битом и столько же другие биты как возможно установлены. Эта эвристика является лишь плохим в том случае, если бы вам потребовалось число из набора с самым значительным битом и несколькими различными менее значимыми битами.

С помощью этой эвристики вы также можете выбрать среди тех наборов наибольшее число 1.... 1 как дополнительную эвристику.

Ответ 2

Позвольте немного обобщить проблему. Я буду писать побитовые операторы, такие как OR и AND и SR (shift right).

Для натурального числа X интервалы [lo_1, hi_1],..., [lo_N, hi_N], состоящие из натуральных чисел и бит b в {0, 1}, определяют, существуют ли натуральные числа y_1 в [ lo_1, hi_1],..., y_N в [lo_N, hi_N], что, если Y = y_1 OR... OR y_N, он считает, что (X и Y) = X и что существует я такое, что x_i <= hi_i - b.

Базовый регистр для моего рекурсивного алгоритма - это когда lo_1 = hi_1 = lo_2 =... = hi_n = 0. Существует решение тогда и только тогда, когда X = 0 и b = 0.

Индуктивно подготавливаем подзадачу, позволяя X '= X SR 1 и lo_i' = lo_i SR 1 и hi_i '= hi_i SR 1. Пусть Odd (i) истинно тогда и только тогда, когда hi_i AND 1 = 1. Пусть Odd + (i) быть истинным тогда и только тогда, когда Odd (i) и lo_i < hi_i. Если X И 1 = 0:

Если существует я такое, что Odd + (i), то пусть b '= 0. В противном случае пусть b' = b.

Если X И 1 = 1:

Если существуют различные я и j такие, что Odd + (i) и Odd (j), то пусть b '= 0. Если не существует j таких, что Odd (j), то пусть b' = 1. В противном случае, пусть b '= b.

Верните ответ для подзадачи.