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

Question

Дано N целочисленных интервалов [lo_i, hi_i].

Из каждого интервала выбирается число, такое, что побитовое ИЛИ из них становится заданным числом X. (Не имеет значения, если результат имеет больше 1 бита, чем X; т.е. если сгенерированное число равно Y, (X & Y) == X должен держать)

Answer 1

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

Учитывая натуральное число 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 ИЛИ ... ИЛИ y_N, оно содержит (X AND Y) = X и существует i, такое что x_i <= hi_i - b. </p>

Базовый случай для моего рекурсивного алгоритма - это когда 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

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

Если Х И 1 = 1:

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

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

Answer 2

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

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

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