Найдите квадратный корень числа с помощью Bit Manipulation

Учитывая неотрицательное целое число N , задача состоит в том, чтобы найти квадратный корень из N , используя побитовые операции. Если целое число не является полным квадратом, вернуть наибольшее целое число, которое меньше или равно квадратному корню из N , т. е. floor( √N ).

Примеры:

Input: N = 36
Output: 6
Explanation:  The square root of 36 is 6.

Input: N = 19
Output: 4
Explanation:  The square root of 19 lies in between
4 and 5 so floor of the square root is 4.

Подход: Чтобы решить проблему с помощью побитовых операторов, следуйте следующей идее:

Let’s assume that square root of N is X i.e., N ≥ X². 
Let’s consider binary representation of X = ( b_m, b_m-1, ….., b₂, b₁, b₀ ) where b_i represents the i^th bit in binary representation of X. Since, the value of each bits can either be 1 or 0, we can represent 
X = ( a_m + a_m-1 + . . . + a₂ + a₁ + a₀ ) where a_i = 2ⁱ or a_i = 0.

Consider an approximate solution:
S_j = ( a_m + a_m-1 + . . . + a_j ) and also let S_j = S_j+1 + 2^j. 
If S_j² ≤ X² ≤ N then j^th bit is set and 2^j is part of the answer. Otherwise, it is 0.

Следуйте приведенной ниже иллюстрации для лучшего понимания.

Иллюстрации:

N = 36  , result = 0
Binary representation of N: 100100
MSB of N is 5.

Initially result = 0, a = 2⁵ = 32

For 5th bit:
    =>(result + a) = (0 + 32) = 32, and 32 * 32 = 1024 is greater than N (36)
    => update a = a/2 = 32/2 = 16, result = 0

For 4th bit:
    => Now, (result + a) = 16, and 16 * 16 = 256 is greater than N (36)
    => update a = a/2 = 16/2 = 8

For 3rd bit:
    => Now, (result + a) = 8, and 8 * 8 = 64 is greater than N (36)
    => update a = a/2 = 8/2 = 4

For 2nd bit:
    => Now, (result + a) = 4, and 4 * 4 = 16 is less than N (36) so add (a) to result 
    => update a = a/2 = 4/2 = 2, result = 4

For 1st bit:
    => Now, (result + a) = (4+2) =6, and 6 * 6 = 36 is equal to N (36) so add (a) to result
    => update a = a/2 = 2/2 = 1, result = 6

So, the final result = 6.

Основываясь на приведенном выше наблюдении в каждой битовой позиции, найдите вклад этого бита в ответ и добавьте это значение к окончательному ответу. Выполните шаги, указанные ниже, чтобы реализовать описанный выше подход:

• Инициализируйте переменную (скажем, результат ), чтобы сохранить окончательный ответ.
• Начните итерацию с MSB N :
  • Если квадрат ( результат + a _i ) не превышает N , то этот бит имеет вклад в результат [где a _i равно 2 ⁱ ].
  • Поэтому добавьте значение a _i в результат .
• После завершения итерации значение, сохраненное в результате , является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O (log N)
Вспомогательное пространство: O(1)