1

say I have a string 42\0 0b0011010000110001000000000 [or an array without a null terminator 42 0b00110100001100010] and I want to convert it to 42 0b00101010 with bit manipulation. How would I go about this?

Charles Staal
  • 338
  • 1
  • 14

3 Answers3

2

In a nutshell, without any checks that the number is a digit, is negative, or will be out of range, you can do this:

int myatoi( const char * s )
{
    int result = 0;
    while( *s )
    {
        result <<= 1;
        result += (result << 2);
        result += (*s++ & 0x0f);
    }
    return result;
}

Caveat: The use of addition doesn't strictly meet the requirement that this be achieved with bit operations.

paddy
  • 60,864
  • 6
  • 61
  • 103
  • I like the elegance of this answer. There's no way to get rid of the addition, right? – Charles Staal Jul 14 '15 at 03:08
  • No easy way. I think any solution you could come up with would be more computationally expensive than this. Usually the reason we jump to bit operations for math is when there's a performance gain that the compiler won't get through aggressive optimizations. For example, a multiply by 10 might be converted to bit shifts by the compiler, but it wouldn't turn `(*s - '0')` into `(*s & 0x0f)` because they would give different output if presented with bad data. – paddy Jul 14 '15 at 03:17
  • yeah I took a look at http://www.geeksforgeeks.org/add-two-numbers-without-using-arithmetic-operators/ and there seems to be more steps than it would take to just through it through the ALU. I'm just doing it as an intellectual exercise. Thanks for your help. I never knew you could iterate through a char* the way you did. Super cool. – Charles Staal Jul 14 '15 at 03:20
  • Regarding performance, and expressing operations the way we _think_ is better, read this: http://stackoverflow.com/q/6357038/1553090 – paddy Jul 14 '15 at 03:21
  • thanks, I'll give it a read. I thought you were kind of stuck up before, but you were just pointing out that I wasn't doing what I set out to do. Thanks so much for your input! – Charles Staal Jul 14 '15 at 03:23
2

Adding on to @paddy 's answer, for a purely bitwise way to accomplish this is this:

#include <stdio.h>

int bitwiseadd(int x, int y);

int main(int argc, char **argv)
{
    char *array = argv[1];
    int result = 0;

    while(*array)
    {
        result <<= 1;
        result = bitwiseadd(result, result<<2);
        result = bitwiseadd(result, *array++ & 0x0f);
    }
    printf("Value is:%d.\n", result);
    return 0;
}

int bitwiseadd(int x, int y)
{
    if( y == 0 )
        return x;
    else
        return bitwiseadd(x^y,(x&y)<<1);
}
Charles Staal
  • 338
  • 1
  • 14
1

I believe this is the answer.

First we need to strip the 0010 off the top, as in the ASCII table the binary of the char is 0010+the binary value of the number, 1 is 00100001 etc So, you would do 00001111 & char; so

int tmpValue = 15 & char;

Next, you would get the size of the array.

int n = strlen(chararray);

working left to right of the array

#include <stdio.h>
#include <string.h>

int main(void)
{
        char array[4] = "123\0";
        int total = 0;
        int index;

        int arraysize = strlen(array);
        for(index=0; index < arraysize; index++)
        {
                total = ((total << 3) + (total << 1));
                total += (15 & array[index]);
        }
        printf("Value is: %d", total);
        return 0;
}
Charles Staal
  • 338
  • 1
  • 14
  • You said you wanted bit manipulation, but then you're multiplying by return from `exp`... You can achieve multiplication using bit shifts, you know. – paddy Jul 14 '15 at 02:41
  • @paddy well no one else is giving any answer so I decided to give it a shot. Excuse me for trying. I'm figuring it out as I go and I will update accordingly. – Charles Staal Jul 14 '15 at 02:44
  • 1
    ANDing with 15 is a nice trick. You can avoid the call to pow by multiplying the current total by 10 using bitshifts, (hint: x * 10 = x * 8 + x * 2), then adding (15 & array[index]) – samgak Jul 14 '15 at 02:46
  • @samgak thanks, I'm going to go eat dinner then finish it up :) – Charles Staal Jul 14 '15 at 02:52
  • @samgak, it would be (x<<3) + (x<<1) ? – Charles Staal Jul 14 '15 at 02:56
  • @samgak, just did that. the total is off by 1 order of magnitude. 123 is coming out to 1230 – Charles Staal Jul 14 '15 at 02:59
  • Your loop condition should be index < arraysize. The last digit you process is index = arraysize - 1 because C arrays start from 0 – samgak Jul 14 '15 at 03:02
  • @samgak just did that and now I'm getting inconsistant output. I'm pushing some bits in to the total that shouldn't be there. weird. – Charles Staal Jul 14 '15 at 03:04
  • Your char array isn't large enough, you need an extra byte for the null – samgak Jul 14 '15 at 03:07
  • You did not provided enough storage to null-terminate your string. The string is 3 bytes plus 1 for the terminator, but your array can only hold 3 bytes, leading to undefined behaviour of `strlen` – paddy Jul 14 '15 at 03:07
  • @samgak there is no way to do it without first null terminating right? Or else it starts throwing some undefined behavior? – Charles Staal Jul 14 '15 at 03:11
  • Your function has to know when to stop processing digits. So you can either have a null-terminated string, or else you can have an array of digit characters and a digit count stored with it (that's how Pascal stores strings). – samgak Jul 14 '15 at 03:14
  • @samgak alright cool ty, that's what I figured. I took a look at how to add with bitwise operators and it's more of a hassle. I'll finish this up tomorrow probably with pure bitwise operators :) – Charles Staal Jul 14 '15 at 03:17