• API
• FAQ
• Tools
• Archive
daily pastebin goal
34%
SHARE
TWEET

# Untitled

a guest Aug 10th, 2018 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. binary roots of an integer
2. N is an integer within the range [1..2,147,483,647].   For example, given N = 3245 the function should return 55.   Complexity:
3.
4.     expected worst-case time complexity is O(sqrt(N));
5.     expected worst-case space complexity is O(1).
6.
7. #include <algorithm>
8. #include <cassert>
9. #include <cmath>
10. #include <cstddef>
11. #include <cstdlib>
12. #include <iostream>
13. #include <limits.h>
14.
15. template <typename UnsignedT>
16. UnsignedT bit_rev(UnsignedT u)
17. {
18.     UnsignedT ret = UnsignedT();
19.
20.     std::size_t n;
21.     for (n = CHAR_BIT * (sizeof (UnsignedT)); n > 0 && !(u & (static_cast<UnsignedT>(0x1) << (n - 1))); --n)
22.         /* empty */;
23.
24.     std::size_t i;
25.     for (i = 0; i < n; ++i) {
26.         ret |= ((u >> i) & 0x1) << (n - i - 1);
27.     }
28.     return ret;
29. }
30.
31. long least_symmetric_binary_root(unsigned long N)
32. {
33.     long ret = -1;
34.
35.     unsigned long floor_sqrt_N = static_cast<unsigned long>(std::sqrt(static_cast<long double>(N)));
36.     while ((floor_sqrt_N + 1) * (floor_sqrt_N + 1) < N) {
37.         ++floor_sqrt_N;
38.     }
39.
40.     unsigned long a;
41.     for (a = 1; a <= floor_sqrt_N; ++a) {
42.         if (N % a == 0) {
43.             unsigned long q = N / a;
44.             if (bit_rev(a) == q) { // `a` is a symmetric binary root of N.
45.                 return a; // We know that it is the least symmetric binary root.
46.                 // Proof:
47.                 // Let (distinct and in ascending order) a_1, ..., a_n be all natural numbers such
48.                 // that a_k <= sqrt(N) and a_k evenly divides N. Let q_k = N / a_k. For all k, q_k >= sqrt(N).
49.                 // Suppose that N is such that at least one of { a_k } is a symmetric binary root (this case).
50.                 // Let a_k be the first symmetric binary root of N (i.e. bit_rev(a_k) == q_k) among a_1, ..., a_n.
51.                 // It could be that some of { q_1, ..., q_n } are symmetric binary roots, but for all j = 1 .. n, q_j >= sqrt(N) >= a_k.
52.                 // Also, for j = k + 1 .. n, a_j > a_k. Therefore, a_k is the least symmetric binary root.
53.             } else if (bit_rev(q) == a) { // `q` is a symmetric binary root of N.
54.                 ret = (ret == -1 ? q : std::min(ret, static_cast<long>(q)));
55.             }
56.         }
57.     }
58.
59.     return ret;
60. }
61.
62. int main()
63. {
64.     assert(bit_rev(0x0U) == 0U);
65.     assert(bit_rev(0x80000000U) == 1U);
66.     assert(bit_rev(0x11U) == 17U);
67.     assert(bit_rev(0x7094FU) == 496775U);
68.     assert(bit_rev(0x2EFDB7U) == 3895261U);
69.
70.     std::cout << least_symmetric_binary_root(50UL) << std::endl;
71.     assert(least_symmetric_binary_root(50UL) == 10L);
72.     std::cout << least_symmetric_binary_root(286UL) << std::endl;
73.     assert(least_symmetric_binary_root(286UL) == 22L);
74.     std::cout << least_symmetric_binary_root(256UL) << std::endl;
75.     assert(least_symmetric_binary_root(256UL) == 256L);
76.
77.     return EXIT_SUCCESS;
78. }
79.
80. #include <stdlib.h>
81. #include <stdio.h>
82. #include <math.h>
83.
84. // bit-reverse a number, the simple way
85. static unsigned long bit_rev(unsigned long n){
86.     unsigned long r = 0;
87.     while(n){
88.         r = (r << 1) | (n&1);
89.         n >>= 1;
90.     }
91.     return r;
92. }
93.
94. // find least symmetric binary root of an odd number
95. static long int odd_sym_root(unsigned long n){
96.     unsigned long root_floor = (unsigned long)sqrt(n), r, q;
97.     // adjust the square root in case it's too small
98.     while(root_floor*(root_floor+2) < n) ++root_floor;
99.     // start at the smallest odd number with the same highest set
100.     // bit as the sqaure root
101.     r = root_floor;
102.     r |= r >> 1;
103.     r |= r >> 2;
104.     r |= r >> 4;
105.     r |= r >> 8;
106.     r |= r >> 16;   // root_floor is < 2^32, so we can stop here
107.     r = ((r+1)/2)|1;
108.     while(r <= root_floor){
109.         q = n/r;
110.         // check if r divides n, the cofactor has the right number
111.         // of bits and finally if it's the bit-reversal of r
112.         if ((n == q*r) && (q < 2*r) && (q == bit_rev(r))){
113.             return r;
114.         }
115.         r += 2;
116.     }
117.     // n has no symmetric binary root
118.     return -1;
119. }
120.
121. static long int least_symmetric_binary_root(unsigned long n){
122.     unsigned long m = n;
123.     unsigned k = 0;
124.     // find the odd part of n
125.     while((m&1) == 0){
126.         ++k;
127.         m >>= 1;
128.     }
129.     // find the least symmetric binary root of odd part
130.     long int r = odd_sym_root(m);
131.     // and shift if it has one
132.     return (r < 0) ? (-1) : (r << k);
133. }
134.
135. int main(int argc, char *argv[]){
136.     unsigned long n = (argc > 1) ? strtoul(argv[1],NULL,0) : 25;
137.     long int r = least_symmetric_binary_root(n);
138.     if (r < 0){
139.         printf("No symmetric binary root.n");
140.     } else {
141.         printf("Least symmetric binary root: %ldn",r);
142.     }
143.     return EXIT_SUCCESS;
144. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top