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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <iostream>
#include <limits>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cassert>
// verify (at compile time) that the type unsigned int holds at least 32 bits
// https://en.cppreference.com/w/cpp/types/numeric_limits/digits
// https://en.cppreference.com/w/cpp/language/static_assert
static_assert( std::numeric_limits<unsigned int>::digits >= 32, "" ) ;
constexpr unsigned int NBITS = 32 ; // #bits required to cater to numbers up to 10^9
// verify (at compile time) that bits 1100 0000 0000 0000 0000 0000 0000 0000 is
// adequate to hold values up to 10^9 that the program requires
static_assert( ( (1U<<(NBITS-1)) + (1U<<(NBITS-2)) ) > 1'000'000'000, "" ) ;
// fill up the vector with numbers that have exactly two unique bits set
// where the lower bit position is at lower_bit_pos
void fill_higher_bit( unsigned int lower_bit_pos, std::vector<unsigned int>& target_numbers )
{
const unsigned int low_bit_value = 1U << lower_bit_pos ;
// for each bit position higher than lower_bit_pos set
for( unsigned int pos = lower_bit_pos + 1 ; pos < NBITS ; ++pos )
target_numbers.push_back( ( 1U << pos ) + low_bit_value ) ;
// compute the integer value of the number and add it to the vector
}
std::vector<unsigned int> make_target_numbers()
{
std::vector<unsigned int> numbers ;
// for each possible bit position for which the less significant bit is set
for( unsigned int lower_bit_pos = 0 ; lower_bit_pos < (NBITS-1) ; ++lower_bit_pos )
fill_higher_bit( lower_bit_pos, numbers ) ;
// fill the vector with all possible candidate numbers where a higher bit is set
// look up for the nearest candidate number would be (slightly) faster
// if the sequence is sorted; we can then do a binary search
std::sort( numbers.begin(), numbers.end() ) ;
return numbers ;
}
int main()
{
const auto start = std::clock() ; // this is just for timing the creation of the look up table
// may be commented out in production code
// https://en.cppreference.com/w/cpp/chrono/c/clock
// https://en.cppreference.com/w/cpp/chrono/c/CLOCKS_PER_SEC
const std::vector<unsigned int> target_numbers = make_target_numbers() ;
// these two lines may be commented out in production code
const auto end = std::clock() ;
std::cout << "creating the look up table (of size " << target_numbers.size() << ") took "
<< (end-start) * 1'000'000.0 / CLOCKS_PER_SEC << " microseconds.\n" ;
// for each number in the initialiser list (the three given test cases,
// and three more arbitrarily chosen numbers thousand, million and billion)
for( unsigned int n : { 10U, 22U, 4U, 1000U, 1'000'000U, 1'000'000'000U } )
{
// https://en.cppreference.com/w/cpp/algorithm/lower_bound
// get the (iterator to) the number in the candidate sequence greater than or equal to n
const auto next = std::lower_bound( target_numbers.begin(), target_numbers.end(), n ) ;
// if n is smaller than the smallest candidate number (3), we need to add one to n
// *next - n times to bring the value up to the smallest candidate number
// note that since next is the iterator, *next gives us the integer value of the number
if( next == target_numbers.begin() ) std::cout << *next - n << '\n' ;
else
{
// run-time sanity check; not required (we have already checked this via a static_assert)
// comment out the next line in production code
assert( target_numbers.back() > 1'000'000'000 ) ;
// get the iterator to the candidate number that is just lower than n
const auto prev = next-1 ;
// the answer is the minimum of the distance between n and either of the two
// candidate numbers. either add one to n (*next - n) times
// or subtract one from n (n - *prev) times
// https://en.cppreference.com/w/cpp/algorithm/min
std::cout << std::min( *next - n, n - *prev ) << '\n' ;
}
}
}
|
