Page MenuHomePhabricator

Add SparseBitVector::find_last()

Authored by zturner on Jan 17 2017, 11:15 AM.



I didn't add a find_prev because I don't need it, although I can without much additional effort. Otherwise, this is pretty self explanatory, just an analogue of find_first() but for searching in reverse.

Diff Detail


Event Timeline

zturner created this revision.Jan 17 2017, 11:15 AM

(Note that I also added some tests for find_last, and while doing so noticed that there were no tests for find_first(), so I added those too.

dberlin added inline comments.Jan 17 2017, 11:33 AM
141 ↗(On Diff #84707)

Don't you really just want counttrailingzeros, and the index is bitword_size - count trailing zeros?

zturner added inline comments.Jan 17 2017, 11:35 AM
141 ↗(On Diff #84707)

I made the same mistake at first. Because the LSB is the bit with the lowest "index", we have to use countLeadingZeros. i.e. 0b00000000000000000000000000000110 has bits 1 and 2 set. The value we want returned from the function is 2.

dberlin accepted this revision.Jan 17 2017, 1:08 PM
dberlin added inline comments.
141 ↗(On Diff #84707)

This assumes we store these little endian.
If we store them big endian, ...

Anyway, i think you are correct, and if not, the test will fail, so :)

This revision is now accepted and ready to land.Jan 17 2017, 1:08 PM
This revision was automatically updated to reflect the committed changes.