How to convert e.g. number 75 to base 4 representation? The result should be 1023. I plan to use uint32_t
x = a_{3}.4^{3} + a_{2}.4^{2} + a_{1}.4^{1} + a_{0}.4^{0} = a_{3}.64 + a_{2}.16 + a_{1}.4 + a_{0}
How to convert e.g. number 75 to base 4 representation? The result should be 1023. I plan to use uint32_t
x = a_{3}.4^{3} + a_{2}.4^{2} + a_{1}.4^{1} + a_{0}.4^{0} = a_{3}.64 + a_{2}.16 + a_{1}.4 + a_{0}
Last edited by barracuda; 03-13-2015 at 02:52 PM.
The most convenient way is to convert the number to binary first.
for instance :
You wish to convert to base 4 which means that each two bits(in the binary form) represent a single digit in your base 4 representation.Code:75 = 01001011
Code:01 00 10 11 //binary 1 0 2 3 //base 4
If both the original number and the result fit into uint32_t then it's quite simple.
You just repeatedly modulo and divide by 4, until the original number becomes zero. This will get you the digits in reverse order. You only have to reverse the digits after this.
Code:75%4 = 3 (a0) 75/4=18 18%4 = 2 (a1) 18/4=4 4%2 = 0 (a2) 4/4=1 1%4 = 1 (a3)
"Highbrow philosophical truth: Everybody is an ape in monkeytown" --Oscar Wilde
No, I disagree. The most convenient way, in my opinion, is to do it right-to-left.
The rightmost digit of value, in any base, is value modulo base.
In C99, the result of the modulo operation, value % base, has the same sign as value, so you must first make sure value is nonnegative. If the original value was negative, just prepend a negative sign to the result string (as the final operation).
Converted to a string, you need a char buffer of at least (size_t)ceil(2.0 + log((double)base)/log(2.0) * CHAR_BIT * (double)sizeof value) chars, including the string-terminating nul char. If the caller supplies the buffer, and the conversion ends up using fewer chars, you can use memmove() to move the string to the origin of the buffer. I normally don't, I just document that my integer-to-string conversion function returns a valid pointer within the specified buffer, not necessarily to the beginning of the buffer.
(For base 10, I approximate that using 3+39*CHAR_BIT*sizeof value/128. For base 4, I'd use 3+CHAR_BIT*sizeof value/2. These are compile-time constant expressions, and therefore valid to use as the size of a char buffer. These work for bignum libraries, too.)
@Aslaville
Wow, that's awesome! I thought about something like:
Not tested.Code:char rchar[5]; int remainder, number, x, c; remainder = number= 75; c=-1; if ( remainder >= 64 ){ x = (int) (number/64); remainder = number-x; } else x=0; c++; rchar[c]= ... (x) ...; // digit to char if ( remainder >= 16 ){ x = (int) (number/16); remainder = number-x; } else x=0; c++; rchar[c]= ... (x) ...; // digit to char if ( remainder >= 4 ){ x = (int) (number/4); remainder = number-x; } else x=0; c++; rchar[c]= ... (x) ...; // digit to char c++; rchar[c]= ... (remainder) ...; // digit to char
I don't know how convert digit do char.
Still division is there (slower). Your calculation should be much simpler.
How do you convert binary '01' to char '1'?
Last edited by barracuda; 03-14-2015 at 03:35 AM.
This is best and fastest solution:
I doubt you could find fastest solution. No division, no modulo, no loops. It just does what I need, to get 4 digits in base 4 from number 75.Code:uint16_t k,kk,kkk,kkkk; unsigned char a,b,c,d; k=kk=kkk=kkkk = 75; a = k & ~(0b11111100); b = (kk & ~(0b11110011)) >> 2 ; c = (kkk & ~(0b11001111)) >> 4; d = (kkkk & ~(0b00111111)) >> 6;
Edit: This one is faster - 0.044624s !!!
Code:m=4000x4000; for (;n<m;n++){ k = 75; a = k & 0b11; b = (k & 0b1100) >> 2 ; c = (k & 0b110000) >> 4; d = (k & 0b11000000) >> 6; }
Last edited by barracuda; 03-14-2015 at 01:58 PM.
Make sure you use the -O compiler flag and it will even be faster because the compiler will optimize everything.
the result of the optimization:
Code:.file "b4.c" .section .rodata.str1.1,"aMS",@progbits,1 .LC0: .string "%d = %c %c %c %c base 4" .text .globl main .type main, @function main: .LFB11: .cfi_startproc movl $16000000, %eax .L2: subl $1, %eax jne .L2 pushl %ebp .cfi_def_cfa_offset 8 .cfi_offset 5, -8 movl %esp, %ebp .cfi_def_cfa_register 5 andl $-16, %esp subl $32, %esp movl $51, 20(%esp) movl $50, 16(%esp) movl $48, 12(%esp) movl $49, 8(%esp) movl $75, 4(%esp) movl $.LC0, (%esp) call printf movl $0, %eax leave .cfi_restore 5 .cfi_def_cfa 4, 4 ret .cfi_endproc .LFE11: .size main, .-main .ident "GCC: (Debian 4.7.2-5) 4.7.2" .section .note.GNU-stack,"",@progbits