Побитовая интервальная арифметика
Если вы НЕ хотите сливаться с другой таблицей, а скорее вставляете новые данные ... Я придумал это. Возможно, лучший способ сделать это?
MERGE INTO TABLE1 a
USING DUAL
ON (a.C1_pk= 6)
WHEN NOT MATCHED THEN
INSERT(C1_pk, C2,C3,C4)
VALUES (6, 1,0,1);
2 ответа
Для интервала [a мин ], max ] неотрицательных целых чисел, мы можем вычислить побитовый минимум a 0 , где биты независимо устанавливаются в 0 всякий раз, когда это возможно в пределах интервала. Точно так же мы можем вычислить побитовый максимум a 1 , где биты установлены на 1 как можно больше в интервале. Для [b min , b max ] мы делаем то же самое и получаем b 0 и b 1 . Тогда интервал результата будет [a 0 | b 0 , a 1 | b 1 ].
Легко проверить для бита, какие значения он может принимать для a из [a min , a max ]. Для бита n, если все биты m с m> = n совпадают в min и max , то значение принудительно устанавливается, иначе оно может быть 0 или 1.
Это можно сделать за O (n).
Подписанный футляр предоставляется читателю в качестве упражнения. Первый шаг - дать определение того, что означают поразрядные операторы для отрицательных целых чисел.
Изменить: К сожалению, это неверно: рассмотрим случай, когда [a min , a max ]] = [b min , b ] max ] = [1,2].
Тогда a | b может быть 1, 2 или 3, но побитовый минимум равен 0.
Аргх. Вы уверены, что это должны быть целые числа со знаком? Это просто вызывает кучу надоедливых случаев, когда вам нужно что-то переворачивать.
Если мы ограничимся целыми числами без знака, мы можем просто просмотреть биты, чтобы найти максимум. Любой бит выше самого высокого бита, установленного в max (a_max, b_max) , очевидно, не может быть включен. Без ограничения общности предположим, что a_max> b_max. Сохраните все биты в a_max, пока мы не достигнем самого высокого бита в b_max. Затем сохраните все биты обоих, пока у нас не будет гибкости хотя бы с одной стороны (т.е. мы сможем выбрать число в разрешенном диапазоне, которое изменит этот бит). Если другая сторона не может установить этот бит в 1, установите его в 1 и продолжайте работу (установка одного старшего бита всегда превосходит установку всех младших битов). В противном случае установите свой ответ (этот бит - 1), в результате чего все остальные биты будут помещены в 1, и все готово.
Теперь мы делаем то же самое для минимума, за исключением того, что мы избегаем установки битов при каждой возможности, но используем любую возможность для объединения битов, если одна сторона должна установить единицу.
Это O (n) по количеству битов, если мы можем вычислить целые числа за O (1) раз. В противном случае это O (n ^ 2).
Вот как это работает на вашем примере [2,3] | [8,9]
101 -> 1xx works
10 to 11 -> x1x always set ; 11x doesn't fit in a so we're not done
11 can set last bit -> 111
100 -> 1xx must be set
10 to 11 -> x1x must be set ; 11x doesn't fit so we're not done
10 has xx0 as does 100 -> xx0 works -> 110
Изменить: добавление битов знака не меняет порядок алгоритма, но требует более утомительной бухгалтерии. Если вы не можете избавиться от знакового бита, вы меняете минимальную и максимальную стратегии (то есть устанавливать или не устанавливать биты). Если это необязательно, минимальное значение - это когда вы устанавливаете его, а затем пытаетесь не устанавливать все остальное; максимум - это когда вы отключите его, а затем попытаетесь оставить все остальное установленным.
Вторая правка: вот еще один пример; оба диапазона [1001,1100]:
Must keep first bit -> 1xxx
Can set 2nd bit -> x1xx
Other _could have but did not need to_ set 2nd bit -> set 2nd bit -1 -> xx11
-> 1111 is max
Must keep first bit -> 1xxx
Neither needs 2nd bit -> x0xx
Neither needs 3rd bit -> xx0x
Both need 4th bit -> xxx1
-> 1001 is min