count_bits_flip.cpp File Reference

Implementation to [Count number of bits to be flipped to convert A to B] (https://www.geeksforgeeks.org/count-number-of-bits-to-be-flipped-to-convert-a-to-b/) in an integer. More...

#include <cassert>
#include <cstdint>
#include <iostream>

Include dependency graph for count_bits_flip.cpp:

Go to the source code of this file.

Namespaces
namespace	bit_manipulation
	for assert
namespace	count_bits_flip
	Functions for the count bits flip implementation.

Functions
std::uint64_t	bit_manipulation::count_bits_flip::countBitsFlip (std::int64_t A, std::int64_t B)
	The main function implements count of bits flip required.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Implementation to [Count number of bits to be flipped to convert A to B] (https://www.geeksforgeeks.org/count-number-of-bits-to-be-flipped-to-convert-a-to-b/) in an integer.

We are given two numbers A and B. Our task is to count the number of bits needed to be flipped to convert A to B.

Explanation:

A = 01010 B = 10100 As we can see, the bits of A that need to be flipped are 01010. If we flipthese bits, we get 10100, which is B.

Worst Case Time Complexity: O(log n) Space complexity: O(1)

Author

Yash Raj Singh

Definition in file count_bits_flip.cpp.

Function Documentation

countBitsFlip()

std::uint64_t bit_manipulation::count_bits_flip::countBitsFlip	(	std::int64_t	A,
		std::int64_t	B )

The main function implements count of bits flip required.

Parameters

A	is the given number whose bits will be flipped to get number B
B	is the given target number

Returns

total number of bits needed to be flipped to convert A to B

Definition at line 43 of file count_bits_flip.cpp.

                  {  // int64_t is preferred over int so that
                       // no Overflow can be there.
 
    int count =
        0;  // "count" variable is used to count number of bits flip of the
            // number A to form B in binary representation of number 'n'
    A = A ^ B;
    while (A) {
        A = A & (A - 1);
        count++;
    }
    return count;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 86 of file count_bits_flip.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 65 of file count_bits_flip.cpp.

                   {
    // A = 10, B = 20 return 4
    assert(bit_manipulation::count_bits_flip::countBitsFlip(10, 20) == 4);
    // A = 20, B = 25 return 3
    assert(bit_manipulation::count_bits_flip::countBitsFlip(20, 25) == 3);
    // A = 7, B = 10 return 3
    assert(bit_manipulation::count_bits_flip::countBitsFlip(7, 10) == 3);
    // A = 17, B = 25 return 1
    assert(bit_manipulation::count_bits_flip::countBitsFlip(17, 25) == 1);
    // A = 11, B = 8 return 2
    assert(bit_manipulation::count_bits_flip::countBitsFlip(11, 8) == 2);
    // A = 21, B = 22 return 2
    assert(bit_manipulation::count_bits_flip::countBitsFlip(21, 22) == 2);
    // A = 7, B = 786 return 5
    assert(bit_manipulation::count_bits_flip::countBitsFlip(7, 786) == 5);
    std::cout << "All test cases successfully passed!" << std::endl;
}