# 2019q1W7上: 陳冠廷

## 測驗 `1`

static inline size_t find_next_bit(const unsigned long *bitmap,
                                   size_t bits,
                                   size_t start)
{
    unsigned long t;
    size_t l = BITS_TO_LONGS(bits);
    size_t first_long = start / BITS_PER_LONG;
    size_t long_lower = start - (start % BITS_PER_LONG);

    if (start >= bits)
        return bits;

    t = bitmap[first_long] & BITMAP_FIRST_WORD_MASK(start);
    for (size_t i = first_long + 1; !t && i < l; i++) {
        t = bitmap[i];
        long_lower += BITS_PER_LONG;
    }

    if (!t)
        return bits;

    size_t pos;
    size_t offset;
    offset = bitops_ffs(t);
    if (offset) {
      offset--;
    }
    else {
      offset = BITS_PER_LONG;
    }
    pos = (long_lower + offset) > bits ? bits : (long_lower + offset);

    return pos;
}

## 測驗 `2`

:::info
參考資訊: [urandom](https://linux.die.net/man/4/urandom): Linux 核心提供的亂數產生器
:::

#include <unistd.h>
#include <fnctl.h>

int main(void) {
    int fd = open("/dev/urandom", O_RDONLY);
    size_t n;
    for (size_t i = 1; i < MAX_TEST_BITS; i++) {
        read(fd, &n, 4);
        n = n % MAX_TEST_BITS;

        bitmap_fill(test, i);
        assert(find_next_bit(test, i, 0) == 0);

        if (n >= i)
          assert(find_next_bit(test, i, n) == i);
        else
          assert(find_next_bit(test, i, n) == n);

        bitmap_zero(test, i);
        assert(find_next_bit(test, i, 0) == i);

        if (n >= i)
          assert(find_next_bit(test, i, n) == i);
        else
          assert(find_next_bit(test, i, n) == i);
    }
    return 0;
}

## 測驗 `3`

static inline size_t bitops_ffs(unsigned long x) {
    unsigned n = 0;
    if (!x) return 0;

    if (!(x & 0x00000000ffffffff)) n += 32, x >>= 32;
    if (!(x & 0x000000000000ffff)) n += 16, x >>= 16;
    if (!(x & 0x00000000000000ff)) n += 8,  x >>= 8;
    if (!(x & 0x000000000000000f)) n += 4,  x >>= 4;
    if (!(x & 0x0000000000000003)) n += 2,  x >>= 2;
    if (!(x & 0x0000000000000001)) n += 1,  x >>= 1;

    return n + 1;
}

## 測驗 `4`

/**
 * bitops_ffz() - find (least significant) first zero bit plus one
 * @x: unsigned long to check
 *
 * Return: plus-one index of first zero bit; zero when x is ULONG_MAX
 */
static inline size_t bitops_ffz(unsigned long x) {
    return bitops_ffs(~x);
}