# Thread: how compute base 4?

1. ## how compute base 4?

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

x = a3.43 + a2.42 + a1.41 + a0.40 = a3.64 + a2.16 + a1.4 + a0

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

x = a3.43 + a2.42 + a1.41 + a0.40 = a3.64 + a2.16 + a1.4 + a0
The most convenient way is to convert the number to binary first.

for instance :

Code:
`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.

Code:
```01  00  10  11   //binary

1   0    2    3   //base 4```

3. 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)```

4. Originally Posted by Aslaville
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.)

5. Originally Posted by Nominal Animal
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.

6. @Aslaville

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

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```
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'?

8. This is best and fastest solution:
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;```
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 !!!

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

9. Originally Posted by barracuda
This is best and fastest solution:
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;```
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 !!!

Code:
```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

10. 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```