Determine if a number ends with "1" using bitwise operators

Question

How can I determine if the last digit of a decimal number is 1, given arbitrary numbers such as 21, 81, 35, 123, using only rudimentary bit operators?

My objective is to get more comfortable with bit operations such as xor, and as well as shifting.

The problem I'm facing is that some numbers will have the least significant bit set even though they do not end with the decimal digit one, otherwise the last digit could be determined with a mask like this:

>>> '{0:08b}'.format( 5 & 1)
'00000001'
>>> '{0:08b}'.format( 500231 & 1)
'00000001'

Obviously, I'm a little confused, and would like some pointers on how to solve this problem. The example code is in Python, but suggestions and possible answers can be in any language including natural English.

What I have tried so far:

>>> def go():
...     for i in [35,123,01,11,21,31,41,51,61,71,81,91,101]:
            endswith1(i)

def endswith1(code):
    #   ...
    #   xxxxx
    # & 00111
    # ^ 00001
    #   00000
    filter = code & 7
    isone = filter ^ 1
    a =  'and 7: {0:08b}'.format( filter)
    x =  'xor 1: {0:08b}'.format( isone )
    b =  '{0:08b}'.format( code)
    one = isone == 0
    print '%3d:%s %12s %12s %s' %( code,b,  a,x, one) 
    #return ((code & 7) ^ 1 ) == 0

>>> go()
 35:00100011 and 7: 00000011 xor 1: 00000010 False
123:01111011 and 7: 00000011 xor 1: 00000010 False
  1:00000001 and 7: 00000001 xor 1: 00000000 True
 11:00001011 and 7: 00000011 xor 1: 00000010 False
 21:00010101 and 7: 00000101 xor 1: 00000100 False
 31:00011111 and 7: 00000111 xor 1: 00000110 False
 41:00101001 and 7: 00000001 xor 1: 00000000 True
 51:00110011 and 7: 00000011 xor 1: 00000010 False
 61:00111101 and 7: 00000101 xor 1: 00000100 False
 71:01000111 and 7: 00000111 xor 1: 00000110 False
 81:01010001 and 7: 00000001 xor 1: 00000000 True
 91:01011011 and 7: 00000011 xor 1: 00000010 False
101:01100101 and 7: 00000101 xor 1: 00000100 False

The *actual problem* is to determine if a chess piece is a pawn where all pieces are encoded as pawn: 01, knight: 02, bishop: 03, rook: 04, queen: 05, king: 06 and 81, 82, 83, 84, 85, 86 for the black counterparts. The example function solves the problem, but I figured it would be interesting to generalize the function for all possible numbers. I thought the problem was trivial, but two hours later I can't nail it with a simple solution. — Ярослав Рахматуллин, Oct 04 '13 at 00:45
There is nothing wrong with n % 10 == 1, but % is not a bitwise operator. — Ярослав Рахматуллин, Oct 04 '13 at 00:47
This is actually an interesting question and I'd love to know the answer too (curiosity...). My first guess would be to see how % is implemented at a base level (say, circuitry), and then convert `n % 10` to that. — William Gaul, Oct 04 '13 at 00:48
@WilliamGaul % is a part of the `div` instruction and is usually implemented in the ALU. http://stackoverflow.com/questions/5608559/division-and-modulus-using-single-divl-instruction-i386-amd64 — nonsensickle, Oct 04 '13 at 00:52
@WilliamGaul: on x86 it's a byproduct of the DIV/IDIV opcodes, so probably it just performs the division, but compilers typically use magic tricks to avoid using DIV, since it's slow. gcc for `n%10` emits [some scary code](http://pastebin.com/pBcHV3f1) that uses a MUL by `0xCCCCCCCD` and several ADD and SUB. I read in a reverse engineering book that often divisions by known constants are implemented like that (also, there was a handy table of "magic constants" and an explanation of how this works). — Matteo Italia, Oct 04 '13 at 00:52
Is there some reason you don't want to encode pieces as powers of 2, greatly simplifying the checks you need to perform? You could also leverage that mechanism to have a single black/white bit, making it easier to implement code that operates on either color. — jpmc26, Oct 04 '13 at 00:54
^ this. Using a decimal-based encoding and trying to hack it with binary tools is definitely a bad idea; encoding the chess pieces as a power of 2 is way more sensible - you simplify insertion/extraction (it becomes a trivial bitmask) *and* waste less space. You could use 4 bit for piece (3 bits for piece kind, one for black/white), so 2 pieces per byte; this would allow you to keep a whole chessboard in 32 bytes. — Matteo Italia, Oct 04 '13 at 00:59
http://en.wikipedia.org/wiki/Bitboard for more... Btw, you guys are right on `div`, but that would probably be hard to replicate in high level code. — William Gaul, Oct 04 '13 at 01:01
@MatteoItalia I'm probably just missing something since I'm not that familiar with bit level operations, but wouldn't it take 6 bits (1 per piece) plus a black/white bit? Pawn = 0b000001, Knight = 0b000010, Bishop = 0b000100, etc. plus the black/white bit? — jpmc26, Oct 04 '13 at 01:09
@jpmc26: nope, you are encoding it as a bitfield, but it's not necessary - there can't be more than one piece in the same cell; just keep the encoding explained above (with numbers from 0 to 6, which stay in 3 bits) and stick a binary 1 in front of them (i.e. bitwise or with 8) if it's a black piece. 4 bits in total. To get the piece kind (regardless of the color) you do an AND with 7 (cleaning the 4th bit), to get the player you do an AND with 8 (and shift to right by 3 positions if you want to get to the 0/1 range). — Matteo Italia, Oct 04 '13 at 01:13
@MatteoItalia But then it's not powers of 2? I should probably stop bothering you and go read something informative, but I'm not clear on what point you're agreeing with. — jpmc26, Oct 04 '13 at 01:20
@jpmc26: I expressed myself badly in the comment above; you don't need to have powers of two for the pieces, but to divide the bits of information in binary-based fields, that you can easily manipulate with bitwise operations. — Matteo Italia, Oct 04 '13 at 01:23
@MatteoItalia Thanks for your comments. I'm using this format: http://chessprogramming.wikispaces.com/10x12+Board . It's more or less what you have in mind. — Ярослав Рахматуллин, Oct 04 '13 at 01:25
@ЯрославРахматуллин: yes, that's the idea, although there you keep just one piece per byte to allow for other information useful to implement efficiently the gameplay in the top 4 bits. By the way, [here's](http://pastebin.com/Xp1Jwc10) a quick implementation of how my (trivial) idea above would be implemented in C. — Matteo Italia, Oct 04 '13 at 01:34

score 1 · Answer 1 · answered Oct 04 '13 at 00:51

I think the problem is that you're trying to do a decimal operation on a hexadecimal value. If you convert the hex number to BCD (binary coded decimal), then you'll have something that you can mask against 0x0001 and see if the final digit is a 1.

There's a bitwise version of this for VHDL at http://fayazkadir.com/blog/?p=2439

It is... mighty long. But I think porting that would give you what you want.

nonsensickle · Answer 2 · 2013-10-04T01:15:48.443

0

Using bitwise operators in this situation would be inefficient. If you are after an exercise in using them then I recommend using @DanielWeaver's answer.

The n % 10 == 1 operation could translate to a single instruction on your machine. The div instruction documented here and here will place the remainder of the division in the top half of the register for you. However, as @MatteoItalia points out, your compiler avoids this instruction because it is slow. Please see his comment below for how your compiler treats the n % 10 == 1 line.

You could use this slower instruction form in inline assembly or @DanielWeaver's answer instead.

The reason that bitwise operators are not ideal is, as @DanielWeaver points out, because they operate on raw binary numbers.

edited Oct 04 '13 at 01:15

answered Oct 04 '13 at 01:01

nonsensickle

4,438
2
34
61

1

It's true that `DIV` *can* be used to perform this operation, but the compiler avoids it at all costs since the "generic division" opcode is slow. [This](http://pastebin.com/pBcHV3f1) is what gcc generates for `return (i%10)==1;` with `-O3` (and it doesn't emit `div` even at `-O0`). – Matteo Italia Oct 04 '13 at 01:02
Ok, it seems like I forgot about this part. It has been a while since I dealt with x86 assembly. Thanks for pointing it out. I've updated my answer. – nonsensickle Oct 04 '13 at 01:16

Gianluca Ghettini · Answer 3 · 2013-10-10T15:53:51.653

here the solution: no modulo 10 involved

I'll work with the number 617283950 = 100100110010110000000101101110.

First split the number into odd and even bits (I'm calling "even" the bits corresponding to even powers of 2):

   100100110010110000000101101110
    0 1 0 1 0 0 1 0 0 0 1 1 0 1 0 even
   1 0 0 1 0 1 1 0 0 0 0 0 1 1 1  odd

Now in each of these, add and subtract the digits alternately, as in the standard test for divisibility by 11 in decimal (starting with addition at the right):

   100100110010110000000101101110
   +0-1+0-1+0-0+1-0+0-0+1-1+0-1+0 = -2
  +1-0+0-1+0-1+1-0+0-0+0-0+1-1+1  =  1

Now double the sum of the odd digits and add it to the sum of the even digits:

   2*1 + -2 = 0

If the result is divisible by 5, as in this case, the number itself is divisible by 5.

Since this number is also divisible by 2 (the rightmost digit being 0), it is divisible by 10.

That's how your compiler would optimize (in many cases) a modulo 10 operation :)

William Gaul · Answer 4 · 2013-10-04T01:55:29.173

-1

I couldn't let this go without figuring out at least some way to do this, so I resorted to cheating since you're in Python. Don't kill me please.

# Returns whether num ends with the digit ending
def endsInDigit(num, ending):
    return (int(str(i), 16) & 0xf) == ending

In our specific use case, you could do something like endsInDigit(17, 1) # False or endsInDigit(51, 1) # True.

edited Oct 04 '13 at 01:55

answered Oct 04 '13 at 01:29

William Gaul

3,181
2
15
21

I agree. It's not something a programmer should ever need or want to do. Although conceptually, it's doing the same thing as in Daniel Weaver's answer by interpreting 11 as 0x11, 71 as 0x71, etc. – William Gaul Oct 05 '13 at 05:50

Determine if a number ends with "1" using bitwise operators

How can I determine if the last digit of a decimal number is 1, given arbitrary numbers such as 21, 81, 35, 123, using only rudimentary bit operators?

4 Answers4