Table of Contents
Methods to find the solution
Brute force method
Example
Output
Efficient Method
Explanation of the above code
Conclusion
Home Backend Development C++ Find the number with only set bits between Lth and Rth index using C++

Find the number with only set bits between Lth and Rth index using C++

Aug 26, 2023 pm 09:45 PM
Bit operations c programming digital screening

Find the number with only set bits between Lth and Rth index using C++

In the given problem, we need to find the value of a number that has all the set bits between the given range L, R. For example −

Input: L = 1, R = 5
Output: 62
Explanation: representation of given L and R in binary form is 0..0111110

Input: L = 1, R = 4
Output: 30
Explanation: representation of given L and R in binary form is 0..11110
Copy after login

Methods to find the solution

In the given problem, we will discuss two methods, brute force method and efficient method.

Brute force method

In this method we just iterate over the given range and add up all the powers of 2 in the given range and this will be our answer.

Example

#include<bits/stdc++.h>
using namespace std;
int main() {
   int L = 1, R = 3; // the given range
   int ans = 0; // our answer
   for(int i = L; i <= R; i++) // traversing through the whole range
      ans += pow(2, i); // adding values to the answer.
   cout << ans << "\n";
}
Copy after login
Copy after login

Output

14
Copy after login
Copy after login

In this approach, we just iterate over the range and simply add the powers of 2 of the numbers in the range. The time complexity of this program is O(N), where N is the size of our range. But we can further improve the time complexity by applying bit knowledge in the given problem.

Efficient Method

In this method we will simply construct a formula to calculate our answer.

Example

#include<bits/stdc++.h>
using namespace std;
int main() {
   int L = 1, R = 3; // the given range
   int ans = 0; // our answer
   for(int i = L; i <= R; i++) // traversing through the whole range
      ans += pow(2, i); // adding values to the answer.
   cout << ans << "\n";
}
Copy after login
Copy after login

Output

14
Copy after login
Copy after login

In this method, we formulate a formula to calculate the answer.

Explanation of the above code

As you know we need to count the numbers with set bits in the given range, so in this method we find a Bits are set to the number. We then need to subtract a number with all bits set from 1 to (L-1), so we formulate this observation. The overall time complexity of the given code is O(1), which is constant time complexity, which means we can compute any answer in constant time.

Conclusion

This article will write a program for "only numbers with set bits between L-th and R-th indexes". We also learned a C program and complete methods (common and efficient) to solve this problem. We can write the same program in other languages ​​like C, Java, Python and others. Hope you find this article helpful.

The above is the detailed content of Find the number with only set bits between Lth and Rth index using C++. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial
1664
14
PHP Tutorial
1268
29
C# Tutorial
1243
24
Use C++ to write code to find the Nth non-square number Use C++ to write code to find the Nth non-square number Aug 30, 2023 pm 10:41 PM

We all know numbers that are not the square of any number, such as 2, 3, 5, 7, 8, etc. There are N non-square numbers, and it is impossible to know every number. So, in this article, we will explain everything about squareless or non-square numbers and ways to find the Nth non-square number in C++. Nth non-square number If a number is the square of an integer, then the number is called a perfect square. Some examples of perfect square numbers are -1issquareof14issquareof29issquareof316issquareof425issquareof5 If a number is not the square of any integer, then the number is called non-square. For example, the first 15 non-square numbers are -2,3,5,6,

Inversion algorithm for right rotation of array written in C++ Inversion algorithm for right rotation of array written in C++ Sep 08, 2023 pm 08:17 PM

In this article, we will learn about the reversal algorithm to rotate a given array to the right by k elements, for example −Input:arr[]={4,6,2,6,43,7,3,7},k= 4Output:{43,7,3,7,4,6,2,6}Explanation:Rotatingeachelementofarrayby4-elementtotherightgives{43,7,3,7,4,6,2,6}.Input:arr[]={8 ,5,8,2,1,4,9,3},k=3Output:{4,9,3,8,5,8,2,1} Find the solution

In C programming, find the area of ​​a circle In C programming, find the area of ​​a circle Aug 25, 2023 pm 10:57 PM

A circle is a closed figure. All points on a circle are equidistant from a point inside the circle. The center point is called the center of the circle. The distance from a point to the center of a circle is called the radius. Area is a quantitative representation of the span of dimensions of a closed figure. The area of ​​a circle is the area enclosed within the dimensions of the circle. The formula to calculate the area of ​​a circle, Area=π*r*r To calculate the area, we give the radius of the circle as input, we will use the formula to calculate the area, algorithm STEP1: Takeradiusasinputfromtheuserusingstdinput.STEP2: Calculatetheareaofcircleusing, area=(

A brief analysis of bit operations (bitwise operators) in Golang A brief analysis of bit operations (bitwise operators) in Golang Feb 24, 2023 pm 07:42 PM

In the good old days when computer memory was expensive and processing power was limited, using hacker-style bit operations to process information was the preferred way (and in some cases the only way). To this day, the direct use of bit operations is still an integral part of many computing fields, such as low-level system programming, graphics processing, cryptography, etc.

Written in C++, find the number of quadruples whose first three terms are arithmetic sequences and the last three terms are geometric sequences. Written in C++, find the number of quadruples whose first three terms are arithmetic sequences and the last three terms are geometric sequences. Aug 30, 2023 pm 02:09 PM

In this article we will describe all possible ways to find quaternions, using A.P. for the first 3 terms and G.P. for the last 3 terms. First, we will explain the basic definitions of arithmetic progression (A.P.) and geometric progression (G.P.). Arithmetic Progression (A.P.) - It is a sequence of numbers in which the common difference (d) is the same or constant, meaning that the difference of two consecutive numbers is constant. For example: 1,3,5,7,9|d=2 Geometric Progression (G.P.) - This is a sequence of numbers where the common ratio (r) is the same, which means we can multiply the previous number with a fixed number. For example: 3, 6, 12, 24, ....|r=2 In this problem, we need to determine how many are in the array arr[] of N integers

Write a code using C++ to find the number of subarrays with the same minimum and maximum values Write a code using C++ to find the number of subarrays with the same minimum and maximum values Aug 25, 2023 pm 11:33 PM

In this article, we will use C++ to solve the problem of finding the number of subarrays whose maximum and minimum values ​​are the same. The following is an example of the problem −Input:array={2,3,6,6,2,4,4,4}Output:12Explanation:{2},{3},{6},{6},{2 },{4},{4},{4},{6,6},{4,4},{4,4}and{4,4,4}arethesubarrayswhichcanbeformedwithmaximumandminimumelementsame.Input:array={3,3, 1,5,

Reverse doubly linked list grouping by given size using C++ Reverse doubly linked list grouping by given size using C++ Sep 04, 2023 am 09:49 AM

In this problem, we are given a pointer to the head of the linked list and an integer k. In a group of size k, we need to reverse the linked list. For example -Input:1<->2<->3<->4<->5(doublylinkedlist),k=3Output:3<->2<->1<->5<->4 looking for solutions Method In this problem, we will formulate a recursive algorithm to solve this problem. In this method we will use recursion and solve the problem using recursion. Example#include<iostream&

Find the number of unique pairs in an array using C++ Find the number of unique pairs in an array using C++ Sep 07, 2023 am 11:53 AM

We need proper knowledge to create several unique pairs in array syntax of C++. While finding the number of unique pairs, we count all the unique pairs in the given array i.e. all possible pairs can be formed where each pair should be unique. For example -Input:array[]={5,5,9}Output:4Explanation:Thenumberoffalluniquepairsare(5,5),(5,9),(9,5)and(9,9).Input:array[]= {5,4,3,2,2}Output:16 Ways to Find Solution There are two ways to solve this problem, they are −

See all articles