0

I'm doing some work with tesseral arithmetic and I need to detect carries in specific areas of a word. Because of the nature of the program, the bits' locations depend on the input. For example, with a 32 bit word size and say, an input of 6 bits, I'd be interested in checking bits 19 and 3 for addition carries and bits 31 and 15 for subtraction (more generally, the interesting bits are (word size - 1), (word size / 2 + input bits / 2), (word size / 2 - 1) and (input bits / 2)).

What I'm thinking is something along the lines of:

  (after addition)         ((NumberToCheck & (1 << 19 + 1 << 3)) != 0)  --> carried bit(s)

  (or after subtraction)   ((NumberToCheck & (1 << 31 + 1 << 15)) != 0) --> carried bit(s)

Is there a better approach to this?

bendicott
  • 369
  • 2
  • 17

1 Answers1

1

You can find all carry-ins from integers a, b and their sum s by calculating carry-ins = a XOR b XOR s.

Naturally, carry-ins are also the carry-outs from the immediately preceding bit positions.

The most significant carry-out (which indicates unsigned overflow) can be determined with, in C/C++ speak, most-significant-carry-out = (a > 0xFF...FF - b), where 0xFF...FF is the appropriate maximum value and a and b are non-negative values.

Subtraction can be reduced to addition. See my answers to this question and this question.

Community
  • 1
  • 1
Alexey Frunze
  • 61,140
  • 12
  • 83
  • 180
  • I'm not sure this approach will do what I need; as I'm working with tesseral arithmetic, I'm first unshuffling the bits in the word I'm working on. Then, I need to check for carries in two locations at once; one for the x coordinate and one for the y. In the above example, I'd have something like 00000xxx00000xxxb (where each x is some meaningful value and each 0 is not), so assigning a maximum number would only help with the left subword. – bendicott Mar 02 '12 at 02:13
  • If it helps, I'm also only interested in positive space, so a and b will always be positive values. Each subword will only ever be incremented or decremented by one, which further simplifies things - I know where the carries will occur, if they do. I'm mostly interested in speed; is there a better way to check for changes to these specific bits? (Sorry for double posting; it wouldn't fit in one comment) – bendicott Mar 02 '12 at 02:13