select_64bit.hpp

Go to the documentation of this file.

#pragma once

#include <cstdint>
#include <tudocomp/util.hpp>

namespace tdc {

// thiss linear shifting approach is indeed the fastest, compared with
// a binary search approach and one using __builtin_ffs / __builtin_ctz

constexpr uint8_t SELECT_FAIL = 0xFF;

template<typename uint_t>
inline constexpr uint8_t select1(uint_t v, uint8_t k) {
    DCHECK(k > 0) << "order must be at least one";
    uint8_t pos = 0;
    while(v) {
        if(v&1) {
            if(!--k) return pos;
        }
        ++pos;
        v >>= 1;
    }
    return SELECT_FAIL; //TODO: throw error?
}

template<typename uint_t>
inline constexpr uint8_t select1(uint_t v, uint8_t l, uint8_t k) {
    uint8_t pos = select1(v >> l, k);
    return (pos != SELECT_FAIL) ? (l + pos) : SELECT_FAIL;
}

template<typename uint_t>
inline constexpr uint8_t select0(uint_t v, uint8_t k) {
    DCHECK(k > 0) << "order must be at least one";
    uint8_t pos = 0;
    while(v) {
        if(!(v&1)) {
            if(!--k) return pos;
        }
        ++pos;
        v >>= 1;
    }
    pos += k-1;
    return (pos <= msbf<uint_t>::pos) ? pos : SELECT_FAIL; //TODO: throw error?
}

template<typename uint_t>
inline constexpr uint8_t select0(uint_t v, uint8_t l, uint8_t k) {
    uint8_t pos = select0(v >> l, k);
    if(pos != SELECT_FAIL) {
        pos += l;
        return (pos <= msbf<uint_t>::pos) ? pos : SELECT_FAIL; //TODO: throw error?
    } else {
        return SELECT_FAIL; //TODO: throw error?
    }
}

}