```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 ``` ```// Find square root of a function using binary search. // int b_sqrt(int num); // returns -1 if num is out of range (0 to 1,000,000) // Returns integer part of square root otherwise. #include #include using namespace std; /// b_sqrt /// Calculation square root of an integer using binary search /// @param[in] num Argument /// @ret Integer containing the squareroot of num int b_sqrt(int num) { int ans = -1; if(0 <= num && num <= 1000 * 1000) { ans = 0; int bitfield = 1 << 10; // a rought estimastion of sqrt(1 million) // Alternatively you can initialize bitfield_sq with 1 << 20 // and right shift it by 2 bits everytime to avoid multiplication while(bitfield * bitfield > num) bitfield >>= 1; ans = bitfield; while( 0 != (bitfield >>= 1) ) { ans |= bitfield; if(ans * ans > num) ans ^= bitfield; } } return ans; } int main() { const int sqrtm1 = b_sqrt(-1); if(sqrtm1 != -1) cout << "Failed at -1, expected -1, actual " << sqrtm1 << endl; for(int i = 0; i <= 1000000; ++i) { const int expected = static_cast( sqrt(i) ); const int actual = b_sqrt(i); if(expected != actual) cout << "Failed at " << i << ", expected " << expected << ", actual " << actual << endl; } const int sqrtmillion1 = b_sqrt(1000 * 1000 + 1); if(sqrtmillion1 != -1) cout << "Failed at 1mn+1, expected -1, actual " << sqrtmillion1 << endl; cout << "Problems (if any) are printed above. Rest.... all is well" << endl; return 0; } ```
 ```1 ``` ```Problems (if any) are printed above. Rest.... all is well ```