how compute base 4?

[barracuda]

How to convert e.g. number 75 to base 4 representation? The result should be 1023. I plan to use uint32_t

x = a₃.4³ + a₂.4² + a₁.4¹ + a₀.4⁰ = a₃.64 + a₂.16 + a₁.4 + a₀

[Aslaville]

How to convert e.g. number 75 to base 4 representation? The result should be 1023. I plan to use uint32_t

x = a₃.4³ + a₂.4² + a₁.4¹ + a₀.4⁰ = a₃.64 + a₂.16 + a₁.4 + a₀

The most convenient way is to convert the number to binary first.

for instance :

75 = 01001011

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.

01  00  10  11   //binary 

  1   0    2    3   //base 4

[the_jackass]

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.

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)

[Nominal Animal]

The most convenient way is to convert the number to binary first.

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]

No, I disagree. The most convenient way, in my opinion, is to do it right-to-left.

I would half-heartedly agree that implementing code for the modulo is much easier.

[barracuda]

@Aslaville

Wow, that's awesome! I thought about something like:

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

Not tested.
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'?

[awsdert]

Add the character '0'

[barracuda]

This is best and fastest solution:

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;

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.


Edit: This one is faster - 0.044624s !!!

m=4000x4000;
for (;n<m;n++){
   k = 75;
   a = k & 0b11;
   b = (k & 0b1100) >> 2 ;
   c = (k & 0b110000) >> 4;
   d = (k & 0b11000000) >> 6;
}

[Aslaville]

This is best and fastest solution:

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;

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.


Edit: This one is faster - 0.044624s !!!

m=4000x4000;
for (;n<m;n++){
   k = 75;
   a = k & 0b11;
   b = (k & 0b1100) >> 2 ;
   c = (k & 0b110000) >> 4;
   d = (k & 0b11000000) >> 6;
}

Indeed, you nailed it. Basically if you want the second digit in your base 4 number, save the 3-rd and 4-th bits in the original number

[talahin]

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:

    .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