Или всех пар, образованных путем принятия xor всех чисел в списке.Или всех пар, образованных путем принятия xor всех чисел в списке.
например: 10,15,17
ANS = (10^15) | (15^17) | (10^17) = 31. я сделал o (n * k) algo, но вам нужно что-то лучше, чем это (n - количество записей, а k - нет бит в каждом числе).
Здесь может быть проще всего думать о негативах.
XOR в основном «не равен» - то есть он производит результат 1 тогда и только тогда, когда два входных бита не равны друг другу.
Поскольку вы объединяете все эти результаты вместе, это означает, что вы получаете 1 бит результата в любом месте, где есть как минимум два входа, которые имеют разные значения в этой позиции бита.
Инвертирование этого означает, что мы получаем нуль в только, где каждый вход имеет такое же значение в этой позиции бита.
Чтобы вычислить, что мы можем накапливать два промежуточных значения. Во-первых, мы И вместе все входы. Это даст нам позиции, на которых каждый вход имеет один. Для другого мы инвертируем каждый вход, и И вместе все эти результаты. Это укажет нам каждую позицию, в которой все входы имели значение 0.
ИЛИ те вместе, и мы имеем значение с 1, где каждый вход был равен, и ноль в противном случае.
Инвертируйте это, и мы получим желаемый результат: 0, где все входы равны, и 1, где любое другое.
Это позволяет вычислить результат с линейной сложностью (при условии, что каждое входное значение вписывается в одно слово).
thanx ...... ваше объяснение было очень ясным, и это сработало бы для меня. :) –
«нужно что-то лучше, чем это» довольно неопределенно –
(17^15)? , (15) 10)? ...... не включены? –
@JoseRicardoBustosM. Наверное, потому что это не изменит расчет. '(A^B) == (B^A)'. Итак, '(A^B) | (B^A) 'будет таким же, как' (A^B) '. –