Given a non-negative integer N, the task is to find the square root of N using bitwise operations. If the integer is not the perfect square, return largest integer that is smaller than or equal to square root of N i.e., floor(√N).
Examples:
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.
Approach: To solve the problem using bitwise operators follow the below idea:
Let’s assume that square root of N is X i.e., N ≥ X2.
Let’s consider binary representation of X = ( bm, bm-1, ….., b2, b1, b0 ) where bi represents the ith bit in binary representation of X. Since, the value of each bits can either be 1 or 0, we can represent
X = ( am + am-1 + . . . + a2 + a1 + a0 ) where ai = 2i or ai = 0.Consider an approximate solution:
Sj = ( am + am-1 + . . . + aj ) and also let Sj = Sj+1 + 2j.
If Sj2 ≤ X2 ≤ N then jth bit is set and 2j is part of the answer. Otherwise, it is 0.
Follow the below illustration for a better understanding.
Illustrations:
N = 36 , result = 0
Binary representation of N: 100100
MSB of N is 5.Initially result = 0, a = 25 = 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 = 0For 4th bit:
=> Now, (result + a) = 16, and 16 * 16 = 256 is greater than N (36)
=> update a = a/2 = 16/2 = 8For 3rd bit:
=> Now, (result + a) = 8, and 8 * 8 = 64 is greater than N (36)
=> update a = a/2 = 8/2 = 4For 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 = 4For 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 = 6So, the final result = 6.
Based on the above observation in each bit position find the contribution of that bit in the answer and add that value to the final answer. Follow the steps mentioned below to implement the above approach:
- Initialize a variable (say result) to store the final answer.
- Start iterating from the MSB of N:
- If the square of (result + ai) is at most N then that bit has contribution in the result [where ai is 2i].
- So add the value ai in result.
- After iteration is over, the value stored at result is the required answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find square rootint square_root(int N){ // Find MSB (Most significant Bit) of N int msb = (int)(log2(N)); // (a = 2^msb) int a = 1 << msb; int result = 0; while (a != 0) { // Check whether the current value // of 'a' can be added or not if ((result + a) * (result + a) <= N) { result += a; } // (a = a/2) a >>= 1; } // Return the result return result;}// Driver Codeint main(){ int N = 36; // Function call cout << square_root(N); return 0;} |
C
// C code to implement the approach#include <math.h>#include <stdio.h>// Function to find square rootint square_root(int N){ // Find MSB(Most significant Bit) of N int msb = (int)(log2(N)); // (a = 2^msb) int a = 1 << msb; int result = 0; while (a != 0) { // Check whether the current value // of 'a' can be added or not if ((result + a) * (result + a) <= N) { result += a; } // (a = a/2) a >>= 1; } // Return the result return result;}// Driver Codeint main(){ int N = 36; // Function call printf("%d\n", square_root(N)); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to find square root static int square_root(int N) { // Find MSB(Most significant Bit) of N int msb = (int)(Math.log(N) / Math.log(2)); // (a = 2^msb) int a = 1 << msb; int result = 0; while (a != 0) { // Check whether the current value // of 'a' can be added or not if ((result + a) * (result + a) <= N) { result += a; } // (a = a/2) a >>= 1; } // Return the result return result; } // Driver Code public static void main(String[] args) { int N = 36; // Function call System.out.println(square_root(N)); }} |
Python3
# Python code to implement the approachimport math# Function to find square rootdef square_root (N): # Find MSB(Most significant Bit) of N msb = int(math.log(N, 2)) # (a = 2 ^ msb) a = 1 << msb result = 0 while a != 0: # Check whether the current value # of 'a' can be added or not if (result + a) * (result + a) <= N : result += a # (a = a / 2) a >>= 1 # Return the result return result# Driver Codeif __name__ == '__main__': N = 36 # Function call print(square_root(N)) |
C#
// C# code to implement the approachusing System;public class GFG{ // Function to find square root static int square_root(int N) { // Find MSB(Most significant Bit) of N int msb = (int)(Math.Log(N) / Math.Log(2)); // (a = 2^msb) int a = 1 << msb; int result = 0; while (a != 0) { // Check whether the current value // of 'a' can be added or not if ((result + a) * (result + a) <= N) { result += a; } // (a = a/2) a >>= 1; } // Return the result return result; } // Driver Code public static void Main() { int N = 36; // Function call Console.WriteLine(square_root(N)); }}// This code is contributed by Ankthon |
Javascript
function square_root(N){ // Find MSB(Most significant Bit) of N let msb = parseInt(Math.log2(N)); // (a = 2^msb) let a = 1 << msb; let result = 0; while (a != 0) { // Check whether the current value // of 'a' can be added or not if ((result + a) * (result + a) <= N) { result += a; } // (a = a/2) a >>= 1; } // Return the result return result;}let N = 36; // Function call let ans = square_root(N); console.log(ans);// This code is contributed by akashish. |
6
Time Complexity: O(log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
