Given an unsigned integer x. Round it down to the next smaller multiple of 8 using bitwise operations only.
Examples:
Input : 35
Output : 32
Input : 40
Output : 40
As 40 is already a multiple of 8. So, no
modification is done.
Solution 1: A naive approach to solve this problem using arithmetic operators is :
Let x be the number then,
x = x – (x % 8)
This will round down x to the next smaller multiple of 8. But we are not allowed to use arithmetic operators.
Solution 2: An efficient approach to solve this problem using bitwise AND operation is: x = x & (-8)
This will round down x to the next smaller multiple of 8. The idea is based on the fact that last three bits in a multiple of 8 must be 0,
Below is the implementation of above idea:
C++
#include <bits/stdc++.h>
using namespace std;
int RoundDown(int& a)
{
return a & (-8);
}
int main()
{
int x = 39;
cout << RoundDown(x);
return 0;
}
|
Java
import java.io.*;
class GFG {
static int RoundDown(int a)
{
return a & (-8);
}
public static void main (String[] args) {
int x = 39;
System.out.println (RoundDown(x));
}
}
|
Python3
def RoundDown(a):
return a & (-8)
if __name__ == '__main__':
x = 39
print(RoundDown(x))
|
C#
using System;
class GFG
{
static int RoundDown(int a)
{
return a & (-8);
}
public static void Main()
{
int x = 39;
Console.Write(RoundDown(x));
}
}
|
PHP
<?php
function RoundDown($a)
{
return ($a & (-8));
}
$x = 39;
echo RoundDown($x);
?>
|
Javascript
<script>
function RoundDown(a)
{
return a & (-8);
}
let x = 39;
document.write(RoundDown(x));
</script>
|
Time Complexity: The time complexity of this approach is O(1)
Auxiliary Space: The space complexity of this approach is O(1)
Another Approach : Using shift operators
To get the next smaller multiple of 8, we can divide the number by 8 and then multiply it by 8.
This can be accomplished using the shift operators as shown below:
C++
#include <bits/stdc++.h>
using namespace std;
int RoundDown(int& a)
{
return (a >> 3) << 3;
}
int main()
{
int x = 39;
cout << RoundDown(x) << endl;
return 0;
}
|
Java
import java.util.*;
class Main {
static int roundDown(int a)
{
return (a >> 3) << 3;
}
public static void main(String[] args) {
int x = 39;
System.out.println(roundDown(x));
}
}
|
Python3
def RoundDown(a):
return (a >> 3) << 3
x = 39
print(RoundDown(x))
|
C#
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
class HelloWorld {
public static int roundDown(int a)
{
return (a >> 3) << 3;
}
static void Main() {
int x = 39;
Console.WriteLine(roundDown(x));
}
}
|
Javascript
function RoundDown(a)
{
return (a >> 3) << 3;
}
let x = 39;
console.log(RoundDown(x));
|
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
