|
| |
|
|
A241216
|
|
Number of d-swaps required to reverse the bits in an n-bit word.
|
|
6
|
|
|
|
0, 1, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 5, 4, 5, 4, 5, 4, 5, 4, 4, 4, 5, 4, 5, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 5, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Over all partitions [p(1), p(2), ..., p(m)] into distinct parts of k >= n - 1, take those such that all numbers -n+1, -n+3, n+5, ..., n-1 can be represented as sum(j=1..m, d(j)*p(j) ) where d(j) \in {-1, 0, +1}.
The choices of the d(j) are usually not unique.
If for a partition into u parts a sequence of representations exists such that every digit d(j) = -1 (for part p(j)) is followed by a digit +1 at p(j) positions later, and every digit +1 is preceded accordingly, then a routine using y steps has been found. a(n) is the minimal such u.
Example for n = 7:
The following sequence of signed representations gives a routine using two steps:
- 2 - 4 == -6
- 4 == -4
+ 2 - 4 == -2
- 2 == -2
== +0
+ 2 == +2
- 2 + 4 == +2
+ 4 == +4
+ 2 + 4 == +6
No subsequence of the following list of signed representations of 16 (where the number -1 and +1 each have two representations) gives a valid routine:
- 2 - 6 - 7 == -15
- 6 - 7 == -13
+ 2 - 6 - 7 == -11
- 2 - 7 == -9
- 7 == -7
+ 2 - 7 == -5
- 2 + 6 - 7 == -3
+ 6 - 7 == -1
- 2 - 6 + 7 == -1
+ 2 + 6 - 7 == +1
- 6 + 7 == +1
+ 2 - 6 + 7 == +3
- 2 + 7 == +5
+ 7 == +7
+ 2 + 7 == +9
- 2 + 6 + 7 == +11
+ 6 + 7 == +13
+ 2 + 6 + 7 == +15
The choice for the representation of -1 is (must match the '-2' at shift 3),
so we have to take
+ 6 - 7 == -1
However, the representation
- 2 - 6 + 7 == -1
would be needed to have three '-6' matching the last three '+6'.
A125173 is an upper bound for this sequence, considering (only) k-splits:
A k-split decomposes a word with m bits as either [m] = [k, m-2*k, k] or as [m] = [k, k]. The operation reversing [k] will reverse both copies, so we can remove one from the list.
For an example, a C-routine for reversing 32-bit words that uses the splits [32]=[15,2,15], [15]=[5,5,5], [5]=[2,1,2], and [2]=[1,1] is
uint revbin32(uint x)
{
uint z;
// code using GCC's binary literals
z = (x ^ (x >> 1)) & 0b01001010010100101010010100101001U;
x ^= z ^ (z << 1);
// [ 2 ] --> [ 1 1 ]
z = (x ^ (x >> 3)) & 0b00011000110001100000110001100011U;
x ^= z ^ (z << 3);
// [ 5 ] --> [ 2 1 2 ]
z = (x ^ (x >> 10)) & 0b00000000001111100000000000011111U;
x ^= z ^ (z << 10);
// [ 15 ] --> [ 5 5 5 ] ~ [ 5 5 5 2 5 5 5 ]
z = (x ^ (x >> 17)) & 0b00000000000000000111111111111111U;
x ^= z ^ (z << 17);
// [ 32 ] --> [ 15 2 15 ]
return x;
}
There are, however, routines that use more than one split at each step:
uint revbin32(uint x)
{
uint z;
z = (x ^ (x >> 1)) & 0b01010000101000010100001010000101U;
x ^= z ^ (z << 1);
// [ 2 ] --> [ 1, 1 ] ~ [ 1, 1, 1, ..., 1, 1 ]
z = (x ^ (x >> 2)) & 0b00110010011001001100100110010011U;
x ^= z ^ (z << 2);
// [ 3 ] --> [ 1, 1, 1 ] and [ 4 ] --> [ 2, 2 ]
// ~ [ 2,2, 1,1,1, 2,2, 1,1,1, 2,2, 1,1,1, 2,2, 1,1,1, 2,2 ]
z = (x ^ (x >> 7)) & 0b00000001111000000011100000001111U;
x ^= z ^ (z << 7);
// [ 11 ] --> [ 4, 3, 4 ] and [ 10 ] --> [ 3, 4, 3 ]
// ~ [ 4,3,4, 3,4,3, 4,3,4 ]
z = (x ^ (x >> 21)) & 0b00000000000000000000011111111111U;
x ^= z ^ (z << 21);
// [ 32 ] --> [ 11, 10, 11 ]
return x;
}
This already indicates that A125173 might not give the minimal values.
The first known example where a(n) < A125173(n) is a(40) = 4 (while A125173(40)=5), because a 40-bit word can be reversed in 4 steps using
ulong revbin40(ulong x)
{
ulong z;
const ulong m01 = 0b0010010010010010010010010010010010010010UL;
const ulong m03 = 0b0001000110001000110001000110001000110001UL;
const ulong m09 = 0b0000000001111000000000111110000000001111UL;
const ulong m27 = 0b0000000000000000000000000001111111111111UL;
z = (x ^ (x >> 1)) & m01; x ^= z ^ (z << 1);
z = (x ^ (x >> 3)) & m03; x ^= z ^ (z << 3);
z = (x ^ (x >> 9)) & m09; x ^= z ^ (z << 9);
z = (x ^ (x >> 27)) & m27; x ^= z ^ (z << 27);
return x;
}
The routine uses the partition [1, 3, 9, 27] of 40, while in A125173 only partitions of 39 are considered. Using the partition [1, 3, 9, .., 3^k] for A003462(k+1) one can find more such examples, the next being a routine for reversing 121-bit words in 5 steps, while A125173(121) = 6.
Terms a(40) and beyond computed with the heuristic that all splits n = 2*s + m (see the Stong link) such that the rules for m and s use "compatible" partitions give all optimal partitions for n if those for m and s are both optimal. Here "compatible" means that either S is a subset of M or M is a subset of S (writing S and M for respectively the sets of parts in the partitions for s and m). Compatible sets S and M satisfy card( S union M ) <= max( card(S), card(M) ).
Warning: the terms for n >= 48 are subject to the condition that dropping all non-optimal partitions in the search does not lead to non-optimal partitions in the search. That is, should a partition combining one or two non-optimal partitions (for s and m) lead to a better partition than all combinations of all optimal partitions for s and m then the corresponding term given would be too large.
This sequence differs from A125173 for n = 40, 53, 88, 106, ... (see A255392).
For n = 1, 2, 3, 7, 9, 27, 40, 53, ... the partitions are unique (see A255393), see A255399 for the number of rules for n..
Positions of records are 1, 2, 4, 8, 16, 44, 100, 268, 676, ... (see A255394).
(End)
|
|
|
LINKS
|
Donald E. Knuth, Problem 11264, Amer. Math. Monthly, vol.114, no.1, p.77, (2007).
|
|
|
FORMULA
|
a(3^k) = k, a(n) > k for n > 3^k.
a(3*n) = a(n) + 1, so a(3^j*n) = a(n) + j.
a(n) <= a(3*n+1) <= a(n) + 2.
a(n) <= a(3*n+2) <= a(n) + 2.
a(n) = k + O(log(log(n))), see the Stong link; the first instances with a(n)=k+2 are for n \in {676, 700, 712, 1924, 1928, 1976, 1996, 2008}.
a(2*n+1) <= a(n) + 1.
a(2^j*n+1) <= a(n) + j.
a(2^j*n) <= a(n) + j.
a(n*m) <= a(n) + a(m).
a( (3^j-1)/2 ) <= j.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Added terms a(17)..a(29) and some formulas, Joerg Arndt, Feb 20 2015
|
|
|
STATUS
|
approved
|
| |
|
|
