C++

Forum

 
 
Set MSB 0

SOURABH PRAKASH PATI (30)
I need to set the MSB of a decimal number to 0
which am taking as input. So i don't know how many bits are there in the binary representation of the number. How can i set its MSB to 0 without having to convert it to binary or doing any long operations?
Moschops (7244)
Typically, given a float or double, the MSB is the sign bit, and zero means positive.

So just make the number positive.

https://en.wikipedia.org/wiki/Sign_bit

Here's some demo code. You can see the bits (in hex form) output. The MSB is set to zero when the double value is positive. The code that sets the MSB to zero is
x = abs(x);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>
#include <cmath>
#include <cstring>
 
int main()
{
	uint64_t u;
    std::cout << std::boolalpha
              << "signbit(+0.0) = " << std::signbit(+0.0) << '\n'
              << "signbit(-0.0) = " << std::signbit(-0.0) << '\n';
              
               double x = -7;
               std::cout << std::boolalpha << "signbit(" << x << ") = " << std::signbit(x) << '\n';
               memcpy(&u, &x, sizeof(x));
               std::cout << "Hex of " << x << " = " << std::hex << u << '\n';
               x = abs(x);
               std::cout << std::boolalpha << "signbit(" << x << ") = " << std::signbit(x) << '\n';
               
  
               memcpy(&u, &x, sizeof(x));
               std::cout << "Hex of " << x << " = " << std::hex << u;
}
Last edited on
Chervil (7320)
I need to set the MSB of a decimal number to 0

Strictly speaking, decimal numbers have digits, not bits.

However, internally inside the computer integers are stored in binary form. There's no need to do any conversion.

So i don't know how many bits are there in the binary representation of the number. How can i set its MSB to 0 without having to convert it to binary or doing any long operations?

Well, you don't need to know how many bits there are.

A standard way to set a bit to zero, is to create a mask where all the bits are ones except for the bit you are interested in, which is set to zero.

How is this done? Well start with an unsigned integer, assign the initial value zero.
1
2
3
 
    unsigned int mask = 0; // all bits are zero
    mask = ~mask;          // flip all bits to one
    mask = mask >> 1;      // shift the bits right by one place

After the right-shift, the leftmost bit position contains zero, all remaining bits are 1.

Now you are ready to begin. Just use the bitwise AND operator & to combine the mask with the value you are interested in. Note, it will be most effective on negative numbers. A positive signed integer will already have the leftmost bit set to zero.
1
2
3
 
    int x = -5;
    x = x & mask;
    cout << "x = " << x << '\n';


This can be a tricky area to get to grips with, trying out lots of different examples will help.

See tutorial for more on bitwise operations:
http://www.cprogramming.com/tutorial/bitwise_operators.html

There's also a nice online convertor for displaying/converting numbers from binary / hexadecimal / decimal which can help to understand the internal representations of negative and positive integers.

https://www.mathsisfun.com/binary-decimal-hexadecimal-converter.html


Duthomhas (13129)
I think OP is trying to find the highest bit set.

This is an operation called "bit scan reverse". There are a number of ways to find it. See https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
#include <bitset>
#include <iostream>

unsigned find_msb( unsigned long long value )
{
  unsigned result = 0;
  while (value >>= 1) result++;
  return result;
}

std::string binary( unsigned long long value, unsigned nbits )
{
  std::bitset<64> bits( value );
  auto s = bits.to_string();
  return s.substr( s.length() - nbits );
}

int main()
{
  while (true)
  {
    std::cout << "\nPlease enter any whole number except zero: ";
    unsigned long long n, new_n;
    std::cin >> n;
    if (!n) break;
    
      unsigned index = find_msb( new_n = n );
      new_n ^= 1ULL << index;
    
    std::cout << "given n        = " << binary(     n, index+1 ) << " (" <<     n << ")\n";
    std::cout << "MSB stripped --> " << binary( new_n, index+1 ) << " (" << new_n << ")\n";
  }
}


Hope this helps.
jonnin (11333)
setting the MSB when the exponents are different won't give consistent results (numerically)

Last edited on
Moschops (7244)
setting the MSB when the exponents are different won't give consistent results (numerically)


Sure, but that's not the requirement :)
Duthomhas (13129)
I read the phrase "decimal number" as "integer". I'm not sure why...
SOURABH PRAKASH PATI (30)
I read the phrase "decimal number" as "integer". I'm not sure why..


Sorry for any confusions .

I need to set the MSB of a decimal number to 0


by decimal i meant base 10 . And am dealing with whole numbers only.

@Duthomhas Ur solution was exactly what i was looking for,thankyou.

Thanks everyone for help.

jonnin (11333)
It is best to use at least semi-c++ terms like double or integer. Decimal, to most people, means floating point.
Last edited on
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
namespace detail
{
    template < typename T >
    constexpr bool is_signed_int_v = std::is_integral<T>::value && std::is_signed<T>::value ;

    template < typename T >
    constexpr bool is_unsigned_int_v = std::is_integral<T>::value && std::is_unsigned<T>::value ;
}

template < typename T >
constexpr typename std::enable_if< detail::is_signed_int_v<T>, T >::type clear_msb( T number )
{ return number & std::numeric_limits<T>::max() ; }

template < typename T >
constexpr typename std::enable_if< detail::is_unsigned_int_v<T>, T >::type clear_msb( T number )
{ return number & ( std::numeric_limits<T>::max() / 2 ) ; }

http://coliru.stacked-crooked.com/a/53394fa879cdbd32
Duthomhas (13129)
@JLBorges
That's pretty sweet, but it doesn't necessarily clear the MS set B.
JLBorges (13770)
> but it doesn't necessarily clear the MS set B

I don't get it.
Could you give an example of a number where the set MSB would not be cleared?
Duthomhas (13129)
12

MSB of 12 (11002) is bit #3 (LSB is #0).
Last edited on
JLBorges (13770)
Ah! We have two different interpretations of what the term "most significant bit" means.

I used this definition: The most significant bit is the value of the 2n-1 bit in an n-bit representation.

That is: if the number 0000000000001100 is represented as std::uint16_t:
the least significant bit is bit #0 and most significant bit is bit #15.

I guess two alternative interpretations are possible according to which:
the least significant bit is bit #2 and most significant bit is bit #3.
the least significant bit is bit #0 and most significant bit is bit #3.
Duthomhas (13129)
Yes, almost.

A machine word has a set number of bits, so for N bits the MSB is #N-1 and the LSB is #0.


A number (like 120) is not the same as a machine word.

    The most significant digit of "120" is the leftmost "1".

    The least significant digit of "120" is always the rightmost whole digit.
    (The first digit to the left of the decimal point. In this case, "0").

You can always add zeros left and right: "000120.000". Those digits are not significant.

An insignificant digit is
    - always zero
    - does not affect the value whether present or absent

A significant digit
    - can be any digit
    - affects the number value whether present or absent


Now you can also ask what the least significant non-zero digit is, which happens to be a common need in computer science. However, this is a qualified term (by specifying "non-zero"). So

    11002

Has four significant digits;
MSB is #3;
LSB is #0;
LS set bit is #2.


Number theory, man. Gotta love it!

[edit] Fixed a typo [/edit]
Last edited on
JLBorges (13770)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
#include <type_traits>
#include <limits>
#include <bitset>

namespace detail
{
    template < typename T >
    constexpr bool is_signed_int_v = std::is_integral<T>::value && std::is_signed<T>::value ;

    template < typename T >
    constexpr bool is_unsigned_int_v = std::is_integral<T>::value && std::is_unsigned<T>::value ;
}

template < typename T >
constexpr typename std::enable_if< detail::is_signed_int_v<T>, T >::type clear_msb( T number )
{ return number & std::numeric_limits<T>::max() ; }

template < typename T >
constexpr typename std::enable_if< detail::is_unsigned_int_v<T>, T >::type clear_msb( T number )
{ return number & ( std::numeric_limits<T>::max() / 2 ) ; }

// ************** added ****************************
template < typename T >
typename std::enable_if< detail::is_unsigned_int_v<T>, T >::type
clear_most_significant_set_bit( T number )
{
    if( number == 0 ) return number ;

    T nbits = 0 ;
    for( auto cpy = number ; cpy >>= 1U ; ++nbits ) ;
    return number & ~( T(1U) << nbits ) ;
}

template < typename T >
typename std::enable_if< detail::is_signed_int_v<T>, T >::type
clear_most_significant_set_bit( T number )
{
    using uint = typename std::make_unsigned<T>::type ;
    return number <= 0 ? clear_msb(number) :
                         T( clear_most_significant_set_bit( uint(number) ) ) ;
}

            number: 11111111010000111001111010110010 (-12345678)
       msb_cleared: 01111111010000111001111010110010 (2135137970)
ms_set_bit_cleared: 01111111010000111001111010110010 (2135137970)
----------
            number: 11111111111111111111100000110000 (-2000)
       msb_cleared: 01111111111111111111100000110000 (2147481648)
ms_set_bit_cleared: 01111111111111111111100000110000 (2147481648)
----------
            number: 11111111111111111111111111111111 (-1)
       msb_cleared: 01111111111111111111111111111111 (2147483647)
ms_set_bit_cleared: 01111111111111111111111111111111 (2147483647)
----------
            number: 00000000000000000000000000000000 (0)
       msb_cleared: 00000000000000000000000000000000 (0)
ms_set_bit_cleared: 00000000000000000000000000000000 (0)
----------
            number: 00000000000000000000000000001100 (12)
       msb_cleared: 00000000000000000000000000001100 (12)
ms_set_bit_cleared: 00000000000000000000000000000100 (4)
----------
            number: 00000000101111000110000101001110 (12345678)
       msb_cleared: 00000000101111000110000101001110 (12345678)
ms_set_bit_cleared: 00000000001111000110000101001110 (3957070)
----------
            number: 1111111111111111111111111111111111111111010000111001111010110010 (18446744073697205938)
       msb_cleared: 0111111111111111111111111111111111111111010000111001111010110010 (9223372036842430130)
ms_set_bit_cleared: 0111111111111111111111111111111111111111010000111001111010110010 (9223372036842430130)
----------
            number: 1111111111111111111111111111111111111111111111111111100000110000 (18446744073709549616)
       msb_cleared: 0111111111111111111111111111111111111111111111111111100000110000 (9223372036854773808)
ms_set_bit_cleared: 0111111111111111111111111111111111111111111111111111100000110000 (9223372036854773808)
----------
            number: 1111111111111111111111111111111111111111111111111111111111111111 (18446744073709551615)
       msb_cleared: 0111111111111111111111111111111111111111111111111111111111111111 (9223372036854775807)
ms_set_bit_cleared: 0111111111111111111111111111111111111111111111111111111111111111 (9223372036854775807)
----------
            number: 0000000000000000000000000000000000000000000000000000000000000000 (0)
       msb_cleared: 0000000000000000000000000000000000000000000000000000000000000000 (0)
ms_set_bit_cleared: 0000000000000000000000000000000000000000000000000000000000000000 (0)
----------
            number: 0000000000000000000000000000000000000000000000000000000000001100 (12)
       msb_cleared: 0000000000000000000000000000000000000000000000000000000000001100 (12)
ms_set_bit_cleared: 0000000000000000000000000000000000000000000000000000000000000100 (4)
----------
            number: 0000000000000000000000000000000000000000101111000110000101001110 (12345678)
       msb_cleared: 0000000000000000000000000000000000000000101111000110000101001110 (12345678)
ms_set_bit_cleared: 0000000000000000000000000000000000000000001111000110000101001110 (3957070)

http://coliru.stacked-crooked.com/a/8614775714ada5b6
Topic archived. No new replies allowed.