Posted on by Kalkicode
Code Bit Logic

Turn off the rightmost set bit

The problem involves manipulating the bits of a given number to turn off the rightmost set bit (also known as the least significant set bit). This operation is often used in low-level programming and optimization tasks. In this article, we will explore the concept of turning off the rightmost set bit in a binary representation of a number using bitwise operations.

Turn off the rightmost active bit

Problem Statement and Description

Given a positive integer, the goal is to unset or turn off the rightmost set bit (1) in its binary representation. For example, if the binary representation of a number is 1010, the rightmost set bit is at the second position (from the right), and the task is to turn it off to get 1000.

Example

Consider the following examples to understand the concept:

  • For the number 10 (binary 1010): The rightmost set bit is at the second position (from the right). After turning it off, the number becomes 8.

  • For the number 15 (binary 1111): The rightmost set bit is at the first position (from the right). After turning it off, the number becomes 14.

  • For the number 320 (binary 101000000): The rightmost set bit is at the sixth position (from the right). After turning it off, the number becomes 256.

Idea to Solve the Problem

The idea to solve the problem involves using bitwise operations, specifically the bitwise AND operator (&). By performing a bitwise AND operation between the given number and the number obtained by subtracting one from it (num - 1), we can effectively turn off the rightmost set bit.

Standard Pseudocode

function changeActiveRightMost(num):
    print "Number :", num
    // Turn off rightmost set bit
    result = num & (num - 1)
    print "Result :", result

Algorithm Explanation

  1. Print the given number for reference.
  2. Perform the bitwise AND operation between the given number (num) and the result of subtracting one from it (num - 1). This operation effectively turns off the rightmost set bit.
  3. Print the resulting number after turning off the rightmost set bit.

Resultant Output Explanation

The provided Java code demonstrates the solution to the "Turn off the rightmost set bit" problem on various test cases:

  • For the number 10 (binary 1010): The rightmost set bit is at the second position (from the right). After turning it off using the bitwise AND operation, the number becomes 8.

  • For the number 15 (binary 1111): The rightmost set bit is at the first position (from the right). After turning it off using the bitwise AND operation, the number becomes 14.

  • For the number 320 (binary 101000000): The rightmost set bit is at the sixth position (from the right). After turning it off using the bitwise AND operation, the number becomes 256.

Code Solution

Time Complexity

The time complexity of the provided algorithm is O(1) because it involves a constant number of bitwise operations regardless of the value of the given number.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment