Binary representation of a given number
Write a program to print a Binary representation of a given number.
Source: Microsoft Interview Set-3
Method 1: Iterative Method:
For any number, we can check whether its ‘i’th bit is 0(OFF) or 1(ON) by bitwise AND it with “2^i” (2 raise to i).
1) Let us take number 'NUM' and we want to check whether it's 0th bit is ON or OFF
bit = 2 ^ 0 (0th bit)
if NUM & bit >= 1 means 0th bit is ON else 0th bit is OFF
2) Similarly if we want to check whether 5th bit is ON or OFF
bit = 2 ^ 5 (5th bit)
if NUM & bit >= 1 means its 5th bit is ON else 5th bit is OFF.
Let us take unsigned integers (32 bits), which consists of 0-31 bits. To print the binary representation of an unsigned integer, start from 31th bit, and check whether 31th bit is ON or OFF, if it is ON print “1” else print “0”. Now check whether 30th bit is ON or OFF, if it is ON print “1” else print “0”, do this for all bits from 31 to 0, finally we will get binary representation of number.
Below is the implementation of the above approach:
// C++ Program for the binary
// representation of a given number
#include <bits/stdc++.h>
using namespace std;
void bin(long n)
{
long i;
cout << "0";
for (i = 1 << 31; i > 0; i = i / 2) {
if ((n & i) != 0) {
cout << "1";
}
else {
cout << "0";
}
}
}
// Driver Code
int main(void)
{
bin(7);
cout << endl;
bin(4);
}
#include <stdio.h>
void bin(long n)
{
long i;
printf("0");
for (i = 1 << 31; i > 0; i = i / 2) {
if ((n & i) != 0) {
printf("1");
}
else {
printf("0");
}
}
}
int main(void)
{
bin(7);
printf("\n");
bin(4);
return 0;
}
public class GFG {
static void bin(long n)
{
long i;
System.out.print("0");
for (i = 1 << 31; i > 0; i = i / 2) {
if ((n & i) != 0) {
System.out.print("1");
}
else {
System.out.print("0");
}
}
}
// Driver code
public static void main(String[] args)
{
bin(7);
System.out.println();
bin(4);
}
}
// This code is contributed by divyesh072019.
def bin_representation(n):
binary_str = "0"
for i in range(31, -1, -1):
if n & (1 << i):
binary_str += "1"
else:
binary_str += "0"
return binary_str
def main():
print(bin_representation(7))
print(bin_representation(4))
if __name__ == "__main__":
main()
using System;
public class GFG {
static void bin(long n)
{
long i;
Console.Write("0");
for (i = 1 << 31; i > 0; i = i / 2) {
if ((n & i) != 0) {
Console.Write("1");
}
else {
Console.Write("0");
}
}
}
// Driver code
static public void Main()
{
bin(7);
Console.WriteLine();
bin(4);
}
}
// This code is contributed by avanitrachhadiya2155
function bin(n) {
let result = "";
for (let i = 1 << 30; i >= 1; i = i / 2) {
if ((n & i) !== 0) {
result += "1";
} else {
result += "0";
}
}
return result;
}
function main() {
console.log("0" + bin(7));
console.log("0" + bin(4));
}
main();
Output
0 0
Time Complexity: O(1)
Auxiliary Space: O(1)
Method 2: Recursive Approach:
Following is recursive method to print binary representation of ‘NUM’.
step 1) if NUM > 1
a) push NUM on stack
b) recursively call function with 'NUM / 2'
step 2)
a) pop NUM from stack, divide it by 2 and print it's remainder.
Below is the implementation of the above approach:
// C++ Program for the binary
// representation of a given number
#include <bits/stdc++.h>
using namespace std;
void bin(unsigned n)
{
/* step 1 */
if (n > 1)
bin(n / 2);
/* step 2 */
cout << n % 2;
}
// Driver Code
int main(void)
{
bin(7);
cout << endl;
bin(4);
}
// C Program for the binary
// representation of a given number
void bin(unsigned n)
{
/* step 1 */
if (n > 1)
bin(n / 2);
/* step 2 */
printf("%d", n % 2);
}
// Driver Code
int main(void)
{
bin(7);
printf("\n");
bin(4);
}
// Java Program for the binary
// representation of a given number
class GFG {
static void bin(int n)
{
/* step 1 */
if (n > 1)
bin(n / 2);
/* step 2 */
System.out.print(n % 2);
}
// Driver code
public static void main(String[] args)
{
bin(7);
System.out.println();
bin(4);
}
}
// This code is contributed
// by ChitraNayal
# Python3 Program for the binary
# representation of a given number
def bin(n):
if n > 1:
bin(n//2)
print(n % 2, end="")
# Driver Code
if __name__ == "__main__":
bin(7)
print()
bin(4)
# This code is contributed by ANKITRAI1
// C# Program for the binary
// representation of a given number
using System;
class GFG {
static void bin(int n)
{
// step 1
if (n > 1)
bin(n / 2);
// step 2
Console.Write(n % 2);
}
// Driver code
static public void Main()
{
bin(7);
Console.WriteLine();
bin(4);
}
}
// This code is contributed ajit
<script>
// Javascript program for the binary
// representation of a given number
function bin(n)
{
// Step 1
if (n > 1)
bin(parseInt(n / 2, 10));
// Step 2
document.write(n % 2);
}
// Driver code
bin(7);
document.write("</br>");
bin(4);
// This code is contributed by divyeshrabadiya07
</script>
<?php
// PHP Program for the binary
// representation of a given number
function bin($n)
{
/* step 1 */
if ($n > 1)
bin($n/2);
/* step 2 */
echo ($n % 2);
}
// Driver code
bin(7);
echo ("\n");
bin(4);
// This code is contributed
// by Shivi_Aggarwal
?>
Output
111 100
Time Complexity: O(log N)
Auxiliary Space: O(log N)
Method 3: Recursive using bitwise operator
Steps to convert decimal number to its binary representation are given below:
- Check n > 0
- Right shift the number by 1 bit and recursive function call
- Print the bits of number
Below is the implementation of the above approach:
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to convert decimal
// to binary number
void bin(unsigned n)
{
if (n > 1)
bin(n >> 1);
printf("%d", n & 1);
}
// Driver code
int main(void)
{
bin(131);
printf("\n");
bin(3);
return 0;
}
// Java implementation of the approach
class GFG {
// Function to convert decimal
// to binary number
static void bin(Integer n)
{
if (n > 1)
bin(n >> 1);
System.out.printf("%d", n & 1);
}
// Driver code
public static void main(String[] args)
{
bin(131);
System.out.printf("\n");
bin(3);
}
}
/*This code is contributed by PrinciRaj1992*/
# Python 3 implementation of above approach
# Function to convert decimal to
# binary number
def bin(n):
if (n > 1):
bin(n >> 1)
print(n & 1, end="")
# Driver code
bin(131)
print()
bin(3)
# This code is contributed by PrinciRaj1992
// C# implementation of above approach
using System;
public class GFG {
// Function to convert decimal
// to binary number
static void bin(int n)
{
if (n > 1)
bin(n >> 1);
Console.Write(n & 1);
}
// Driver code
public static void Main()
{
bin(131);
Console.WriteLine();
bin(3);
}
}
/*This code is contributed by PrinciRaj1992*/
<script>
// JavaScript implementation of the approach
// Function to convert decimal
// to binary number
function bin(n)
{
if (n > 1)
bin(n >> 1);
document.write(n & 1);
}
// Driver code
bin(131);
document.write("<br>");
bin(3);
// This code is contributed by Surbhi Tyagi.
</script>
<?php
// PHP implementation of the approach
// Function to convert decimal
// to binary number
function bin($n)
{
if ($n > 1)
bin($n>>1);
echo ($n & 1);
}
// Driver code
bin(131);
echo "\n";
bin(3);
// This code is contributed
// by Akanksha Rai
Output
10000011 11
Time Complexity: O(log N)
Auxiliary Space: O(log N)
This article is compiled by Narendra Kangralkar.
Contact Us