Nice. I'd forgotten the HAKMEM item. Xoring with 3030...3030, radix 4, is the same as subtracting 30* and negating the digits -- it's the 3s complement (in the even-position digits). Rich ----- Quoting Joerg Arndt <arndt@jjj.de>:
* rcs@xmission.com <rcs@xmission.com> [Jul 13. 2011 11:12]:
[...]
To convert an integer to radix -4, first convert to regular hex, then to base 4. To get to -4, add 303030...30 to the number (in radix 4), propagate any carries, then subtract 303030...30, creating negative digits in the alternating positions. Drop the signs, and reinterpret the digit string as radix -4. [...]
Starting from (HAKMEM, item 128) for radix -2:
static inline ulong bin2neg(ulong x) // binary --> radix(-2) { // mask in radix 2 is ...10101010 const ulong m = 0xaaaaaaaaaaaaaaaaUL; x += m; x ^= m; return x; }
static inline ulong neg2bin(ulong x) // radix(-2) --> binary // inverse of bin2neg() { const ulong m = 0xaaaaaaaaaaaaaaaaUL; x ^= m; x -= m; return x; }
... and just replacing the masks ...
static inline ulong bin_to_radm4(ulong x) // binary --> radix(-4) { // mask in binary is ...110011001100 // mask in radix 4 is ...30303030 const ulong m = 0xccccccccccccccccUL; x += m; x ^= m; return x; }
static inline ulong radm4_to_bin(ulong x) // radix(-4) --> binary // inverse of bin_to_radm4() { const ulong m = 0xccccccccccccccccUL; x ^= m; x -= m; return x; }
... seems to work: (note radix-4 vectors are printed with least sgnificant digit left!)
n: binary(n) radix(-4) 0: ........ ........ = [ 0 0 0 0 ] 1: .......1 .......1 = [ 1 0 0 0 ] 2: ......1. ......1. = [ 2 0 0 0 ] 3: ......11 ......11 = [ 3 0 0 0 ] 4: .....1.. ...111.. = [ 0 3 1 0 ] 5: .....1.1 ...111.1 = [ 1 3 1 0 ] 6: .....11. ...1111. = [ 2 3 1 0 ] 7: .....111 ...11111 = [ 3 3 1 0 ] 8: ....1... ...11... = [ 0 2 1 0 ] 9: ....1..1 ...11..1 = [ 1 2 1 0 ] 10: ....1.1. ...11.1. = [ 2 2 1 0 ] 11: ....1.11 ...11.11 = [ 3 2 1 0 ] 12: ....11.. ...1.1.. = [ 0 1 1 0 ] 13: ....11.1 ...1.1.1 = [ 1 1 1 0 ] 14: ....111. ...1.11. = [ 2 1 1 0 ] 15: ....1111 ...1.111 = [ 3 1 1 0 ] 16: ...1.... ...1.... = [ 0 0 1 0 ] 17: ...1...1 ...1...1 = [ 1 0 1 0 ] 18: ...1..1. ...1..1. = [ 2 0 1 0 ] 19: ...1..11 ...1..11 = [ 3 0 1 0 ] 20: ...1.1.. ..1.11.. = [ 0 3 2 0 ] 21: ...1.1.1 ..1.11.1 = [ 1 3 2 0 ] 22: ...1.11. ..1.111. = [ 2 3 2 0 ] 23: ...1.111 ..1.1111 = [ 3 3 2 0 ] 24: ...11... ..1.1... = [ 0 2 2 0 ] 25: ...11..1 ..1.1..1 = [ 1 2 2 0 ] 26: ...11.1. ..1.1.1. = [ 2 2 2 0 ] 27: ...11.11 ..1.1.11 = [ 3 2 2 0 ] 28: ...111.. ..1..1.. = [ 0 1 2 0 ] 29: ...111.1 ..1..1.1 = [ 1 1 2 0 ] 30: ...1111. ..1..11. = [ 2 1 2 0 ] 31: ...11111 ..1..111 = [ 3 1 2 0 ]
Am I somehow wrong here? (my method seems overly simple when compared to your description).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun