Одно из преимуществ аксессуаров и мутаторов заключается в том, что вы можете выполнять проверку.
Например, если foo
был общедоступным, я мог бы легко установить его на null
, а затем кто-то попытался бы позвонить метод на объекте. Но его больше нет! С помощью метода setFoo
я мог убедиться, что foo
никогда не был установлен в null
.
Аксессоры и мутаторы также допускают инкапсуляцию - если вы не должны видеть значение после его установки (возможно, он установлен в конструкторе, а затем используется методами, но никогда не должен быть изменен), он никогда не будет замечен кем-либо. Но если вы можете разрешить другим классам просматривать или изменять его, вы можете предоставить соответствующий аксессуар и / или мутатор.
Могу ли я сделать это без итерации?
blockquote>Это действительно возможно.
Как я наиболее эффективно определяю позицию набора бит?
blockquote>Вы можете попробовать этот алгоритм. Он разбивает символ пополам, чтобы найти верхний бит, каждый раз переходя на нижнюю половину:
int getTopSetBit(unsigned char b) { int res = 0; if(b>15){ b = b >> 4; res = res + 4; } if(b>3){ b = b >> 2; res = res + 2; } //thanks @JasonD return res + (b>>1); }
Он использует два сравнения (три для
uint16
s, четыре дляuint32
s. ..). и это может быть быстрее, чем ваш цикл.
Основываясь на идее Антона Коваленко (хешированный поиск) и комментария на 6502 (деление медленное), я также предлагаю эту реализацию (8-бит => 3 (g0)
int[] lookup = {7, 0, 5, 1, 6, 4, 3, 2}; int getBitPosition(unsigned char b) { // return lookup[(b | (b>>1) | (b>>2) | (b>>4)) & 0x7]; return lookup[((b * 0x1D) >> 4) & 0x7]; }
или (более крупный LUT, но использует только три члена вместо четырех)
int[] lookup = {0xFF, 0, 1, 4, 2, 0xFF, 5, 0xFF, 7, 3, 0xFF, 0xFF, 6, 0xFF, 0xFF, 0xFF}; int getBitPosition(unsigned char b) { return lookup[(b | (b>>3) | (b>>4)) & 0xF]; }
Это довольно распространенная проблема для шахматных программ, которые используют 64 бита для представления позиций (то есть один 64-разрядный номер для хранения, где все белые пешки, другой для всех черных и т. д.).
При таком представлении иногда требуется найти индекс 0 ... 63 первого или последнего бита набора и существует несколько возможных подходов:
x & 0x00000000ffffffffULL
равен нулю, нет необходимости проверять низкие 32 бита) bsf
и bsr
на x86) Что такое быстрее, однако действительно зависит от вашего оборудования и от реальных случаев использования. Только для 8-битных процессоров и для современного процессора я считаю, что лучше всего найти таблицу поиска с 256 записями ...
Но вы действительно уверены, что это узкое место в вашем алгоритме?
Таблица поиска достаточно проста, и вы можете уменьшить ее размер, если набор значений разрежен. Попробуем использовать 11 элементов вместо 128:
unsigned char expt2mod11_bits[11]={0xFF,0,1,0xFF,2,4,0xFF,7,3,6,5};
unsigned char pos = expt2mod11_bits[b%11];
assert(pos < 8);
assert(1<<pos == b);
Конечно, это не обязательно более эффективно, особенно для 8 бит, но тот же трюк можно использовать для больших размеров, где полная таблица поиска будет ужасно большой. Давайте посмотрим:
unsigned int w;
....
unsigned char expt2mod19_bits[19]={0xFF,0,1,13,2,0xFF,14,6,3,8,0xFF,12,15,5,7,11,4,10,9};
unsigned char pos = expt2mod19_bits[w%19];
assert(pos < 16);
assert(1<<pos == w);
Таблица поиска быстро и просто, когда CHAR_BIT == 8, но в некоторых системах CHAR_BIT == 16 или 32, и таблица поиска становится безумно громоздкой. Если вы рассматриваете таблицу поиска, я бы предложил ее обернуть; сделайте его «функцией таблицы поиска», вместо этого, чтобы вы могли поменять логику, когда вам нужно оптимизировать.
Использование divide и conquer путем выполнения двоичного поиска в отсортированном массиве предполагает сравнение на основе log2 CHAR_BIT
. Этот код более сложный, включая инициализацию массива unsigned char
для использования в качестве таблицы поиска для начала. После инициализации такого массива вы можете использовать bsearch
для поиска, например:
#include <stdio.h>
#include <stdlib.h>
void uchar_bit_init(unsigned char *table) {
for (size_t x = 0; x < CHAR_BIT; x++) {
table[x] = 1U << x;
}
}
int uchar_compare(void const *x, void const *y) {
char const *X = x, *Y = y;
return (*X > *Y) - (*X < *Y);
}
size_t uchar_bit_lookup(unsigned char *table, unsigned char value) {
unsigned char *position = bsearch(lookup, c, sizeof lookup, 1, char_compare);
return position ? position - table + 1 : 0;
}
int main(void) {
unsigned char lookup[CHAR_BIT];
uchar_bit_init(lookup);
for (;;) {
int c = getchar();
if (c == EOF) { break; }
printf("Bit for %c found at %zu\n", c, uchar_bit_lookup(lookup, c));
}
}
P.S. Это звучит как микро-оптимизация. Получите свое решение (абстрагирование операций, требуемых для этих функций), а затем подумайте об оптимизации на основе профилирования. Убедитесь, что профилирование нацелено на систему, над которой будет работать ваше решение, если вы собираетесь сосредоточиться на микрооптимизации, поскольку эффективность микрооптимизации сильно различается, поскольку аппаратное обеспечение отличается даже немного ... Обычно лучше купить более быстрый ПК;)
Самое простое - создать таблицу поиска.
Этот комментарий здесь технически избегает итерации, но кто мы шутим, он по-прежнему делает такое же количество проверок: Как написать базу данных (2) в c / c ++
Закрытая форма будет log2 () , a la, log2() + 1
Но я не уверен, насколько эффективен это - возможно, у процессора есть инструкция для приема логарифмов базы 2?
Основываясь на вычислении log2 в Найдите базу данных 2 целочисленного N-бита в операциях O (lg (N)) :
int getSetBitLocation(unsigned char c) {
// c is in {1, 2, 4, 8, 16, 32, 64, 128}, returned values are {0, 1, ..., 7}
return (((c & 0xAA) != 0) |
(((c & 0xCC) != 0) << 1) |
(((c & 0xF0) != 0) << 2));
}
unsigned getSetBitLocation(unsigned char b) {
unsigned pos=0;
pos = (b & 0xf0) ? 4 : 0; b |= b >>4;
pos += (b & 0xc) ? 2 : 0; b |= b >>2;
pos += (b & 0x2) ? 1 : 0;
return pos;
}
Было бы трудно сделать это без прыжка. Может быть, с последовательностями Брюина?
, если вы определяете
const char bytes[]={1,2,4,8,16,32,64,128}
и используете
struct byte{
char data;
int pos;
}
void assign(struct byte b,int i){
b.data=bytes[i];
b.pos=i
}
, вам не нужно определять позицию установленного бита