Convert to uppercase and lowercase without branching and comparisons

-5

1

Write two functions/programs which take an ASCII code of character (8-bit unsigned integer) and one of them converts char to uppercase and other to lowercase.

That is, they must be equivalent to following functions:

unsigned char toUpper(unsigned char c){
    if (c >= 97 && c <= 122) return c - 32;
    return c;
}
unsigned char toLower(unsigned char c){
    if (c >= 65 && c <= 90) return c + 32;
    return c;
}

However you are not allowed to use branching (ifs, gotos), loops and comparison and logical operators. Recursion, language built-in functions, regular expressions, arrays and objects also not allowed. You may use only arithmetic and bitwise operations on 8-bit unsigned integers.

Score:

1 - for | & ^ ~ >> << operators
1.11 - for + - operators
1.28 - for * operator
1.411 - for / % operators

Answer with lowest total score (for two functions added) wins. If answers with equal score than first (oldest) answer wins.

Somnium

Posted 2014-08-19T13:21:33.817

Reputation: 2 537

This good valid question deserves more upvotes. If you are an anti-micro-optimization kind of a guy, then you shouldn't even be at this question, let alone allowing your own biases and prejudices to cloud your judgement and downvote this legitimate question. Also, off-topicly, I would be very interested (fascinated) to see how you generated those score numbers. I'm not criticizing them, rather, just the opposite, I'm intrigued. Mabey you could comment a link to a resource about it? – Jack Giffin – 2017-08-10T16:13:25.830

@lolzerywowzery How I chose scores: At start I defined approximate scores I want operations should have, like 1, 1.1, 1.3 and 1.4. Then with trial and error I modified them a bit so equal score is unlikely with small operator amount. Checked that in Mathematica. – Somnium – 2017-08-10T18:55:50.773

Are regular expressions allowed? If yes, this is a duplicate of Converting a string to lower-case.

– ProgramFOX – 2014-08-19T13:24:54.237

1@ProgramFOX No. – Somnium – 2014-08-19T13:25:53.233

Answers

3

C, C++ and related languages, 6.22

unsigned char toggle(unsigned char c, unsigned char lo, unsigned char hi)
{
    unsigned char m = (unsigned char)((lo - c) ^ (hi - c)) >> 7;
    return c ^ (m << 5);
}

unsigned char toUpper(unsigned char c)
{
    return toggle(c, 96, 122);
}

unsigned char toLower(unsigned char c)
{
    return toggle(c, 64, 90);
}

Paul R

Posted 2014-08-19T13:21:33.817

Reputation: 2 893

If merging common code allowed, why not share all operators? (char xor(char a, char b){return a^b}) @Somnium – l4m2 – 2018-11-10T17:22:55.343

1Your score is 12.44 - total score for 2 functions. – Somnium – 2014-08-19T15:38:13.017

That seems unreasonable - there is only one instance of each operator, not two, and there was nothing in the rules to forbid factoring out common code. – Paul R – 2014-08-19T16:27:15.233

1One more time I failed writing rules. – Somnium – 2014-08-19T17:44:15.273

8

C and other languages with integer division, 15.204 14.644 14.084 11.864

unsigned char toUpper(unsigned char c){
    return c - ((c/97) ^ (c/123)) << 5;
}

unsigned char toLower(unsigned char c){
    return c + ((c/65) ^ (c/91)) << 5;
}

Martin Ender

Posted 2014-08-19T13:21:33.817

Reputation: 184 808

1Just realized that toUpper gives wrong value for n in range [194 - 245] and toLower for almost all n >= 130. – Somnium – 2014-08-19T14:17:55.473

3@Somnium. Afaik ASCII contains only 128 characters. Everything else is extended ASCII which does not seem to be part of your spec. – Martin Ender – 2014-08-19T14:36:30.380

1@MartinBüttner Forgot about that fact. Then your solution is ok. – Somnium – 2014-08-19T15:36:55.457

2

C, 11.482

My functions I have found before posting question, I hope there will better ones.

unsigned char toUpper(unsigned char c){
    unsigned char a = c - 97;
    return c - ((32 - a / 26) & 32);
}
unsigned char toLower(unsigned char c){
    unsigned char a = c - 65;
    return c + ((32 - a / 26) & 32);
}

Somnium

Posted 2014-08-19T13:21:33.817

Reputation: 2 537

0

C (gcc), 9.042 step score

uchar toUpper(uchar c){
    return c^(((uchar)(c+133)/230)<<5);
}
uchar toLower(uchar c){
    return c^(((uchar)(c+165)/230)<<5);
} // 9.042 step score

Try it online!

C (gcc), 2.11 existance score

uchar sub(uchar a, uchar b) {return a-b;}
uchar shr(uchar a, uchar b) {return a>>b;}
uchar add(uchar a, uchar b) {return sub(a, sub(0, b));}
uchar isneg(uchar a) {return shr(a, 7);}
uchar reach230(uchar a) {return shr(add(isneg(a),isneg(sub(229,a))),1);}
uchar dif(uchar a) {uchar t=reach230(a); t=add(t,t); t=add(t,t); t=add(t,t); t=add(t,t); t=add(t,t); return t;}
uchar toUpper(uchar c){ return sub(c,dif(add(c,133))); }
uchar toLower(uchar c){ return add(c,dif(add(c,165))); }

Try it online!

l4m2

Posted 2014-08-19T13:21:33.817

Reputation: 5 985