Журнал LinuxFormat - перейти на главную

LXF155:Вникать в Erlang

Материал из Linuxformat
Перейти к: навигация, поиск
Подписка на печатную версию
Весь 2015 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Подписка на электронную версию
Весь 2015 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)
Подшивки старых номеров журнала (печатные версии)
Весь 2014 год (12 номеров)
Первое полугодие (6 номеров)
Второе полугодие (6 номеров)


Erlang Опи­сы­ва­ет­ся сле­дую­щей фор­му­лой: функ­цио­наль­ный язык + про­цес­сы

Erlang: Ма­гия би­то­вых строк

Ма­ни­пу­ли­руя би­та­ми и бай­та­ми, Ан­д­рей Уша­ков кол­ду­ет над стро­ка­ми: то пе­ре­стро­ит их в дру­гом по­ряд­ке, то ин­вер­ти­ру­ет...

В этом но­ме­ре мы про­дол­жа­ем наш прак­ти­кум по функ­цио­наль­но­му про­грам­ми­ро­ванию на язы­ке Erlang и раз­бе­рем­ся c«чер­ной ма­ги­ей» би­то­вых строк язы­ка Erlang.

Да­вай­те вспомним, что та­кое би­то­вые стро­ки и для че­го они нуж­ны (бо­лее под­роб­но см. LXF148). Би­то­вые стро­ки – это тип дан­ных, по­зво­ляю­щий ра­бо­тать с низ­ко­уровневы­ми дан­ны­ми бо­лее струк­ту­ри­ро­ван­ным, чем на­бор (мас­сив) байт, спо­со­бом. Это оз­на­ча­ет, что мы мо­жем за­да­вать или из­вле­кать дан­ные пор­ция­ми (ко­то­рые на­зы­ва­ют­ся сег­мен­та­ми) про­из­воль­но­го раз­ме­ра, имею­щи­ми один из пре­до­пре­де­лен­ных ти­пов. За­да­вать сег­мен­ты мы мо­жем как в вы­ра­жениях, так и в опе­ра­ци­ях со­от­вет­ст­вия шаб­ло­ну [pattern-matching], а из­вле­кать дан­ные сег­мен­та­ми – толь­ко в опе­ра­ци­ях со­от­вет­ст­вия шаб­ло­ну. Ка­ж­дый сег­мент со­сто­ит из зна­чения или пе­ре­мен­ной (инициа­ли­зи­ро­ван­ной ли­бо неинициа­ли­зи­ро­ван­ной), раз­ме­ра и спи­ска спе­ци­фи­ка­то­ров, оп­ре­де­ляю­щих тип сег­мен­та. Раз­мер и спи­сок спе­ци­фи­ка­то­ров, оп­ре­де­ляю­щих тип сег­мен­та, яв­ля­ют­ся необя­за­тель­ны­ми; ес­ли ка­кой-то из этих ат­ри­бу­тов не за­дан, то для это­го ат­ри­бу­та бе­рет­ся зна­чение по умол­чанию. У сег­мен­тов, ко­то­рые са­ми яв­ля­ют­ся би­то­вы­ми стро­ка­ми (для них спе­ци­фи­ка­тор ти­па бу­дет ли­бо binary, ли­бо bitstring), раз­мер по умол­чанию – вся би­то­вая стро­ка. По­это­му в опе­ра­ции со­от­вет­ст­вия шаб­ло­ну толь­ко по­следний сег­мент в шаб­лоне мо­жет быть би­то­вой стро­кой с раз­ме­ром по умол­чанию (ина­че непо­нят­но, где дол­жен за­кон­чить­ся сег­мент, яв­ляю­щий­ся би­то­вой стро­кой, и на­чать­ся сле­дую­щий за ним сег­мент).

Так, на­при­мер, пусть X и Y – неинициа­ли­зи­ро­ван­ные пе­ре­мен­ные. Тогда в ре­зуль­та­те вы­полнения вы­ра­жения со­от­вет­ст­вия шаб­ло­ну <<X:1/binary, 2, Y/binary>> = <<1, 2, 3, 4>>, пе­ре­мен­ная X бу­дет иметь зна­чение <<1>>, а пе­ре­мен­ная Y бу­дет иметь зна­чение <<3, 4>>.

Этот при­мер де­мон­ст­ри­ру­ет нам прин­цип по­сле­до­ва­тель­ной об­ра­бот­ки би­то­вых строк: при по­мо­щи опе­ра­ции со­от­вет­ст­вия шаб­ло­ну мы раз­де­ля­ем би­то­вую стро­ку на сег­мен­ты, при­чем по­следний сег­мент име­ет тип би­то­вая стро­ка и раз­мер по умол­чанию. Мы об­ра­ба­ты­ва­ем все сег­мен­ты, кро­ме по­следнего, по­сле че­го вы­зы­ва­ем ре­кур­сив­но об­ра­бот­чик (при по­мо­щи хво­сто­вой ре­кур­сии), но уже для по­следнего сег­мен­та; и так, по­ка не бу­дет вы­бран нере­кур­сив­ный ва­ри­ант для функ­ции об­ра­бот­чи­ка (на­при­мер, ва­ри­ант, об­ра­ба­ты­ваю­щий пустую би­то­вую стро­ку). Эта ме­то­ди­ка по­хо­жа на по­сле­до­ва­тель­ную об­ра­бот­ку спи­сков (и там, и тут ис­поль­зу­ют­ся одни и те же прин­ци­пы).

По­сле крат­ко­го об­зо­ра тео­рии по­ра пе­рей­ти к прак­ти­ке. В ка­че­­ст­ве прак­ти­ки мы рас­смот­рим ряд за­дач, свя­зан­ные с манипу­ля­ци­ей би­та­ми и бай­та­ми в би­то­вых стро­ках и це­лых чис­лах. Спо­соб ре­шения, ко­то­рый мы бу­дем ис­поль­зо­вать в на­ших при­ме­рах, от­ли­ча­ет­ся от спо­со­ба ре­шения та­ких за­дач в та­ких язы­ках, как C/C++ и им по­доб­ные. Обыч­но та­кие за­да­чи ре­ша­ют­ся с ис­поль­зо­ванием по­би­то­вых опе­ра­то­ров «И», «ИЛИ», «НЕ», «ИСКЛЮЧАЮЩЕЕ ИЛИ» и опе­ра­то­ров сдви­га. Та­кой ва­ри­ант ре­шения есть и у нас (язык Erlang со­дер­жит та­кой на­бор опе­ра­то­ров). Но мы пой­дем дру­гим пу­тем: бу­дем ре­шать эти за­да­чи с ис­поль­зо­ванием би­то­вых строк и опе­ра­ций с ними. Но это не оз­на­ча­ет, что мы пол­но­стью от­ка­зы­ва­ем­ся от ис­поль­зо­вания по­би­то­вых опе­ра­то­ров: там, где нам удоб­но их ис­поль­зо­вать, мы бу­дем их ис­поль­зо­вать.

Начнем мы наш прак­ти­кум с за­да­чи оп­ре­де­ления минималь­но­го необ­хо­ди­мо­го ко­ли­че­­ст­ва байт для хранения зна­чения це­ло­го чис­ла.. Оп­ре­де­ление минималь­но­го необ­хо­ди­мо­го ко­ли­че­­ст­ва байт за­ви­сит от то­го, счи­та­ем ли мы ис­ход­ное чис­ло чис­лом со зна­ком или чис­лом без зна­ка.

Оп­ре­де­лить минималь­ное необ­хо­ди­мое ко­ли­че­­ст­во байт для це­ло­го чис­ла без зна­ка – доста­точ­но три­ви­аль­ная за­да­ча: мы бе­рем ис­ход­ное чис­ло, де­лим его на 256, по­сле че­го бе­рем це­лую часть от де­ления и по­вто­ря­ем пре­ды­ду­щую опе­ра­цию. Чис­ло опе­ра­ций, необ­хо­ди­мых, что­бы по­лу­чить 0 в ка­че­­ст­ве це­лой час­ти ре­зуль­та­та де­ления, бу­дет рав­но минималь­но­му необ­хо­ди­мо­му ко­ли­че­­ст­ву байт для хранения по­ло­жи­тель­но­го це­ло­го чис­ла.

Те­перь да­вай­те раз­бе­рем­ся с це­лы­ми чис­ла­ми со зна­ком. Начнем с от­ри­ца­тель­ных чи­сел. От­ри­ца­тель­ные чис­ла хра­нят­ся в до­полнитель­ном ко­де, для ко­то­ро­го спра­вед­ли­во сле­дую­щее ут­вер­ждение: стар­ший байт чис­ла дол­жен быть в диа­па­зоне от 2#10000000 = 128 до 2#11111111 = 255 (или, что то же са­мое, стар­ший бит чис­ла дол­жен быть ра­вен 1). По­это­му пер­вым ша­гом мы мо­жем раз­де­лить от­ри­ца­тель­ное чис­ло на -129 и взять це­лую часть; по­сле это­го с ре­зуль­та­том це­лой час­ти от де­ления по­сту­па­ем точ­но так же, как и с це­лым чис­лом без зна­ка. Чис­ло опе­ра­ций, необ­хо­ди­мых, что­бы по­лу­чить 0 в ка­че­­ст­ве це­лой час­ти ре­зуль­та­та де­ления, бу­дет рав­но минималь­но­му необ­хо­ди­мо­му ко­ли­че­­ст­ву байт для хранения от­ри­ца­тель­но­го це­ло­го чис­ла.

Пе­рей­дем к по­ло­жи­тель­ным це­лым чис­лам. Ес­ли зна­чение стар­ше­го бай­та по­ло­жи­тель­но­го це­ло­го чис­ла ле­жит в диа­па­зоне от 2#10000000 = 128 до 2#11111111 = 255, то та­кое по­ло­жи­тель­ное це­лое чис­ло мы не смо­жем от­ли­чить от от­ри­ца­тель­но­го це­ло­го чис­ла. Что мы мо­жем сде­лать в та­кой си­туа­ции – это до­ба­вить до­полнитель­ный байт со зна­чением 0 в ка­че­­ст­ве стар­ше­го бай­та. По­это­му пер­вым ша­гом мы мо­жем раз­де­лить по­ло­жи­тель­ное чис­ло на 128, и взять це­лую часть; по­сле это­го с ре­зуль­та­том це­лой час­ти от де­ления по­сту­па­ем точ­но так же, как и с це­лым чис­лом без зна­ка. Чис­ло опе­ра­ций, необ­хо­ди­мых, что­бы по­лу­чить 0 в ка­че­­ст­ве це­лой час­ти ре­зуль­та­та де­ления, бу­дет рав­но минималь­но­му необ­хо­ди­мо­му ко­ли­че­­ст­ву байт для хранения по­ло­жи­тель­но­го це­ло­го чис­ла.

При­ве­ден­ный вы­ше ал­го­ритм для це­лых чи­сел без зна­ка реа­ли­зо­ван в функ­ции integer_size/1. Эта функ­ция яв­ля­ет­ся ин­тер­фейс­ной; вся ра­бо­та по под­сче­ту со­дер­жит­ся в функ­ции integer_size/2, реа­ли­зую­щей при­ве­ден­ный вы­ше ал­го­ритм для це­лых чи­сел без зна­ка. Сле­ду­ет от­ме­тить, что функ­ция integer_size/1 со­дер­жит от­дель­ный ва­ри­ант для 0; это сде­ла­но для удоб­ст­ва реа­ли­за­ции под­сче­та.

integer_size(0) -> 1;

integer_size(Number) when is_integer(Number) ->

integer_size(Number, 0).

integer_size(0, ByteCount) -> ByteCount;

integer_size(Number, ByteCount) ->

integer_size(Number div 256, ByteCount + 1).

Прак­ти­че­­ски то же са­мое мож­но ска­зать и о функ­ци­ях integer_signed_size/1 и integer_signed_size/2: пер­вая яв­ля­ет­ся ин­тер­фейс­ной, а вто­рая реа­ли­зу­ет ал­го­ритм для це­лых чи­сел со зна­ком. И точ­но так же, функ­ция integer_signed_size/1 со­дер­жит от­дель­ный ва­ри­ант для 0, ко­то­рый вве­ден для удоб­ст­ва реа­ли­за­ции под­сче­та.

integer_signed_size(0) -> 1;

integer_signed_size(Number) when is_integer(Number) ->

integer_signed_size(Number, 0).

integer_signed_size(Number, ByteCount) when Number < 0 ->

integer_size(Number div -129, ByteCount + 1);

integer_signed_size(Number, ByteCount) when Number > 0 ->

integer_size(Number div 128, ByteCount + 1).

Да­вай­те про­ве­рим, что на­пи­сан­ные на­ми функ­ции ра­бо­та­ют пра­виль­но. Для це­ло­го чис­ла 127 = 2#01111111 минималь­ное необ­хо­ди­мое для хранения ко­ли­че­­ст­во байт рав­но 1 и для слу­чая, когда мы счи­та­ем его чис­лом без зна­ка, и для слу­чая, когда мы счи­та­ем его чис­лом со зна­ком. Про­ве­ря­ем это: вы­зов bit_utils:integer_size(127) воз­вра­ща­ет 1, вы­зов bit_utils:integer_signed_size(127) так­же воз­вра­ща­ет 1.

Возь­мем бо­лее слож­ный при­мер. Для це­ло­го чис­ла 128 = 2#10000000, когда мы счи­та­ем его чис­лом без зна­ка, минималь­ное необ­хо­ди­мое для хранения ко­ли­че­­ст­во байт рав­но 1, а в слу­чае, когда мы счи­та­ем его чис­лом со зна­ком, минималь­ное необ­хо­ди­мое для хранения ко­ли­че­­ст­во байт рав­но уже 2. Про­ве­ря­ем это: вы­зов bit_utils:integer_size(128) воз­вра­ща­ет 1, а вы­зов bit_utils:integer_signed_size(128) воз­вра­ща­ет 2. Те­перь про­ве­рим для от­ри­ца­тель­ных чи­сел. Для хранения от­ри­ца­тель­но­го чис­ла -128 = 2#10000000 доста­точ­но 1 бай­та, тогда как для хранения от­ри­ца­тель­но­го чис­ла -129 = 2#1111111101111111 уже необ­хо­ди­мо 2 бай­та. Про­ве­ря­ем это: вы­зов bit_utils:integer_signed_size(-128) воз­вра­ща­ет 1, а вы­зов bit_utils:integer_signed_size(-129) воз­вра­ща­ет 2.

По­сле ре­шения пре­ды­ду­щей за­да­чи мы мо­жем ре­шить дру­гую, свя­зан­ную с ней за­да­чу: соз­дать би­то­вую стро­ку, со­дер­жа­щую зна­чение ис­ход­но­го це­ло­го чис­ла. Для ре­шения этой за­да­чи мы долж­ны знать ко­ли­че­­ст­во байт, необ­хо­ди­мое для пред­став­ления ис­ход­но­го це­ло­го чис­ла. Ес­ли при соз­дании сег­мен­та (с ти­пом integer), ко­то­рый дол­жен со­дер­жать це­лое чис­ло, мы не за­да­дим раз­мер сег­мен­та, то бу­дет ис­поль­зо­ван раз­мер по умол­чанию (для це­лых чи­сел это 8 бит), и сег­мент бу­дет со­дер­жать толь­ко млад­ший байт це­ло­го чис­ла. Так, на­при­мер, би­то­вая стро­ка <<256/integer>> бу­дет рав­на би­то­вой стро­ке <<0>>. По­это­му при по­строении би­то­вой стро­ки, со­дер­жа­щей зна­чение це­ло­го чис­ла, знание минималь­но­го необ­хо­ди­мо­го для хранения это­го це­ло­го чис­ла раз­ме­ра яв­ля­ет­ся обя­за­тель­ным. Обя­за­тель­ным яв­ля­ет­ся так­же знание по­ряд­ка хранения байт и яв­ля­ет­ся ли ис­ход­ное чис­ло чис­лом со зна­ком. Оба эти па­ра­мет­ра неза­ви­си­мые и пе­ре­да­ют­ся в ка­че­­ст­ве ис­ход­ных па­ра­мет­ров в на­шу функ­цию. Сле­ду­ет ска­зать, что па­ра­метр, оп­ре­де­ляю­щий, яв­ля­ет­ся ли ис­ход­ное чис­ло чис­лом со зна­ком, влия­ет на то, ка­кой ал­го­ритм вы­чис­ления минималь­но­го необ­хо­ди­мо­го ко­ли­че­­ст­ва байт для хранения це­ло­го чис­ла бу­дет ис­поль­зо­ван.

Эта за­да­ча реа­ли­зо­ва­на в функ­ции integer_to_binary/3. Функ­ция доста­точ­но три­ви­аль­на: в за­ви­си­мо­сти от ис­ход­ных па­ра­мет­ров, оп­ре­де­ляю­щих по­ря­док байт, и яв­ля­ет­ся ли ис­хо­дя­щее це­лое чис­ло чис­лом без зна­ка, мы вы­чис­ля­ем минималь­ное необ­хо­ди­мое ко­ли­че­­ст­во байт для хранения ис­ход­но­го це­ло­го чис­ла и кон­ст­руи­ру­ем со­от­вет­ст­вую­щую би­то­вую стро­ку.

integer_to_binary(Number, Signedness, ByteOrder) when is_integer(Number) ->

case {Signedness, ByteOrder} of

{signed, big} ->

IntegerSize = 8 * integer_signed_size(Number),

<<Number:IntegerSize/signed-integer-big>>;

{signed, little} ->

IntegerSize = 8 * integer_signed_size(Number),

<<Number:IntegerSize/signed-integer-little>>;

{unsigned, big} ->

IntegerSize = 8 * integer_size(Number),

<<Number:IntegerSize/unsigned-integer-big>>;

{unsigned, little} ->

IntegerSize = 8 * integer_size(Number),

<<Number:IntegerSize/unsigned-integer-little>>

end.

Да­вай­те про­ве­рим, что на­ше ре­шение пра­виль­но. Для чис­ла 128, ес­ли счи­тать это чис­ло чис­лом без зна­ка, мы долж­ны по­лу­чить сле­дую­щую би­то­вую стро­ку: <<128>>. Вы­зов bit_utils:integer_to_binary(128, unsigned, big) воз­вра­ща­ет нам <<128>>. Ес­ли же мы счи­та­ем чис­ло 128 чис­лом со зна­ком, то мы долж­ны по­лу­чить би­то­вую стро­ку <<0, 128>>, при усло­вии, что по­ря­док байт у нас от стар­ше­го бай­та к млад­ше­му [big-endian]. Вы­зов bit_utils:integer_to_binary(128, signed, big) воз­вра­ща­ет нам <<0, 128>>. Для чис­ла -128 мы долж­ны по­лу­чить би­то­вую стро­ку <<128>>, а для чис­ла -129 – би­то­вую стро­ку <<255, 127>> (при усло­вии, что по­ря­док байт у нас от стар­ше­го бай­та к млад­ше­му). Вы­зов bit_utils:integer_to_binary(-128, signed, big) воз­вра­ща­ет нам <<128>>; вы­зов bit_utils:integer_to_binary(-129, signed, big) воз­вра­ща­ет <<255, 127>>.

Пой­дем даль­ше: зай­мем­ся те­перь за­да­ча­ми, свя­зан­ны­ми непо­сред­ст­вен­но с би­то­вы­ми стро­ка­ми. В ка­че­­ст­ве пер­вой та­кой за­да­чи мы возь­мем сле­дую­щую: из­менение по­ряд­ка сле­до­вания байт в би­то­вой стро­ке с раз­ме­ром, крат­ным 8 бит. Ре­шение этой за­да­чи три­ви­аль­ное: мы пре­об­ра­зу­ем би­то­вую стро­ку в спи­сок це­лых чи­сел (ка­ж­дый эле­мент спи­ска яв­ля­ет­ся пред­став­лением со­от­вет­ст­вую­ще­го 8-бит­но­го сег­мен­та в ви­де це­ло­го чис­ла), ме­ня­ем по­ря­док сле­до­вания эле­мен­тов в спи­ске на об­рат­ный и пре­об­ра­зу­ем спи­сок це­лых об­рат­но в би­то­вую стро­ку.

reverse_bytes(Binary) when is_binary(Binary) ->

list_to_binary(lists:reverse(binary_to_list(Binary))).

Те­перь мы мо­жем про­ве­рить, что на­ша функ­ция кор­рект­но ра­бо­та­ет: вы­зов bit_utils:reverse_bytes(<<1, 2, 3>>) да­ет впол­не ожи­дае­мый ре­зуль­тат <<3, 2, 1>>.

Да­вай­те усложним пре­ды­ду­щую за­да­чу: бу­дем ме­нять по­ря­док сле­до­вания бит в би­то­вой стро­ке на об­рат­ный. За­ме­тим, что сле­дую­щие дей­ст­вия да­ют тот же ре­зуль­тат, что и ре­шение «в лоб»: раз­де­ля­ем би­то­вую стро­ку на 8-би­то­вые сег­мен­ты (и воз­мож­ный оста­ток, раз­мер ко­то­ро­го мень­ше 8 бит), ме­ня­ем по­ря­док сле­до­вания сег­мен­тов на об­рат­ный и, для ка­ж­до­го сег­мен­та, ме­ня­ем по­ря­док сле­до­вания би­тов в нем на об­рат­ный. По­сле че­го со­би­ра­ем спи­сок сег­мен­тов об­рат­но в би­то­вую стро­ку. Раз­де­лить би­то­вую стро­ку на 8-би­то­вые сег­мен­ты и воз­мож­ный оста­ток (раз­мер ко­то­ро­го будет мень­ше 8 бит) мы мо­жем с по­мо­щью BIF bitstring_to_list/1.

reverse_bits(Bitstring) when is_bitstring(Bitstring) ->

Segments = bitstring_to_list(Bitstring),

ReversedSegments = lists:map(fun reverse_segment/1, lists:reverse(Segments)),

list_to_bitstring(ReversedSegments).

Для из­менения по­ряд­ка сле­до­вания бит в ка­ж­дом эле­мен­те спи­ска сег­мен­тов мы ис­поль­зу­ем функ­цию reverse_segment/1 (эту функ­цию мы ис­поль­зу­ем из lists:map/2 для пре­об­ра­зо­вания сег­мен­тов с нор­маль­ным по­ряд­ком бит в сег­мен­ты с об­рат­ным по­ряд­ком бит). Эта функ­ция име­ет ва­ри­ант для це­лых чи­сел, т. к. обыч­ные 8-бит­ные сег­мен­ты в спи­ске у нас пред­став­ле­ны в ви­де це­лых чи­сел, и ва­ри­ан­ты для об­ра­бот­ки би­то­вых сег­мен­тов раз­ме­ром от 1 до 8 бит.

reverse_segment(Number) when is_integer(Number) ->

reverse_segment(<<Number:8>>);

reverse_segment(<<B7:1, B6:1, B5:1, B4:1, B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1, B4:1, B5:1, B6:1, B7:1>>;

reverse_segment(<<B6:1, B5:1, B4:1, B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1, B4:1, B5:1, B6:1>>;

reverse_segment(<<B5:1, B4:1, B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1, B4:1, B5:1>>;

reverse_segment(<<B4:1, B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1, B4:1>>;

reverse_segment(<<B3:1, B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1, B3:1>>;

reverse_segment(<<B2:1, B1:1, B0:1>>) ->

<<B0:1, B1:1, B2:1>>;

reverse_segment(<<B1:1, B0:1>>) ->

<<B0:1, B1:1>>;

reverse_segment(<<B0:1>>) ->

<<B0:1>>.

Те­перь при­шла по­ра про­ве­рить, что на­ша реа­ли­за­ция ал­го­рит­ма из­менения по­ряд­ка бит в би­то­вом сло­ве ра­бо­та­ет пра­виль­но. В ка­че­­ст­ве ис­ход­ной би­то­вой стро­ки возь­мем стро­ку <<1, 2, 3:4>>. В дво­ич­ном пред­став­лении она име­ет сле­дую­щий вид: <<2#00000001, 2#00000010, 2#0011>>. По­сле из­менения по­ряд­ка сле­до­вания бит на об­рат­ный эта би­то­вая стро­ка в дво­ич­ном пред­став­лении при­мет вид <<2#1100, 2#01000000, 2#10000000>>. По­сле пе­ре­груп­пи­ров­ки сег­мен­тов со­глас­но пра­ви­лам пред­став­ления би­то­вых строк в язы­ке Erlang (когда оста­ток, не крат­ный 8 бит, идет в кон­це) би­то­вая стро­ка в дво­ич­ном пред­став­лении бу­дет иметь вид <<2#11000100, 2#00001000, 2#0000>>, а в де­ся­тич­ном пред­став­лении – <<196, 8, 0:4>>. Вы­зов bit_utils:reverse_bits(<<1, 2, 3:4>>) да­ет ожи­дае­мый ре­зуль­тат <<196, 8, 0:4>>. Это да­ет нам пра­во счи­тать, что на­ша реа­ли­за­ция ра­бо­та­ет пра­виль­но.

Да­вай­те пе­рей­дем к сле­дую­щей за­да­че: по­счи­та­ем ко­ли­че­­ст­во бит со зна­чением 1 в би­то­вой стро­ке (чи­та­тель мо­жет обоб­щить эту за­да­чу и реа­ли­зо­вать функ­цию по под­сче­ту ко­ли­че­­ст­ва бит с оп­ре­де­лен­ным зна­чением в би­то­вой стро­ке). Са­мо по се­бе ре­шение этой за­да­чи доста­точ­но три­ви­аль­но: необ­хо­ди­мо ре­кур­сив­но (при по­мо­щи хво­сто­вой ре­кур­сии) об­ра­бо­тать би­то­вую стро­ку, вы­де­ляя пер­вый бит и оста­ток. Реа­ли­за­ция со­сто­ит из двух функ­ций: setbit_count/1 и setbit_count/2. Пер­вая яв­ля­ет­ся ин­тер­фейс­ной функ­ци­ей, а вто­рая при по­мо­щи раз­ных ва­ри­ан­тов оп­ре­де­ления функ­ции реа­ли­зу­ет ре­шение дан­ной за­да­чи.

setbit_count(Bitstring) when is_bitstring(Bitstring) ->

setbit_count(Bitstring, 0).

setbit_count(<<>>, Count) -> Count;

setbit_count(<<1:1, Rest/bitstring>>, Count) ->

setbit_count(Rest, Count + 1);

setbit_count(<<0:1, Rest/bitstring>>, Count) ->

setbit_count(Rest, Count).

Мож­но эту за­да­чу ре­шить дру­гим спо­со­бом: с по­мо­щью вы­ра­жения кон­ст­руи­ро­вания би­то­вой стро­ки [Bitstring Comprehensions]. В этом вы­ра­жении ис­точником бу­дет ис­ход­ная би­то­вая стро­ка, из ко­то­рой мы бу­дем из­вле­кать сег­мен­ты раз­ме­ром 1 бит, а фильт­ром бу­дет вы­ра­жение, про­пускаю­щее толь­ко те сег­мен­ты, ко­то­рые со­дер­жат 1. Ко­ли­че­­ст­во бит со зна­чением 1 бу­дет рав­но длине по­лу­чен­ной би­то­вой стро­ки, ко­то­рую мы мо­жем под­счи­тать при по­мо­щи BIF bit_size/1. Вы­гля­дит это вы­ра­жение сле­дую­щим об­ра­зом (здесь Bitstring – пе­ре­мен­ная, со­дер­жа­щая ис­ход­ную би­то­вую стро­ку): bit_size(<< <<Bit:1>> || <<Bit:1>> <= Bitstring, Bit == 1 >>).

Те­перь мож­но про­ве­рить ра­бо­ту на­шей функ­ции. Би­то­вая стро­ка <<2#110010101:9>> со­дер­жит 5 бит со зна­чением 1. Вы­зов bit_utils:setbit_count(<<2#110010101:9>>) да­ет нам число 5.

Да­вай­те рас­смот­рим еще па­ру по­доб­ных за­дач: под­счи­та­ем ко­ли­че­­ст­во ве­ду­щих и за­вер­шаю­щих би­тов со зна­чением 0 в би­то­вой стро­ке. Эти за­да­чи схо­жи с пре­ды­ду­щей ре­шением: мы ре­кур­сив­но (при по­мо­щи хво­сто­вой ре­кур­сии) об­ра­ба­ты­ва­ем би­то­вую стро­ку, вы­де­ляя пер­вый или по­следний (в за­ви­си­мо­сти от за­да­чи) бит и оста­ток. От­ли­ча­ет эти за­да­чи от пре­ды­ду­щей усло­вие пре­кра­щения ра­бо­ты: ес­ли в пре­ды­ду­щей за­да­че мы пол­но­стью про­хо­ди­ли по би­то­вой стро­ке, то в рас­смат­ри­вае­мых в дан­ный мо­мент за­да­чах мы пре­кра­ща­ем об­ра­бот­ку, как толь­ко нам встре­тит­ся бит со зна­чением 1. Что ин­те­рес­но, дан­ные две за­да­чи ре­шить с по­мо­щью вы­ра­жения кон­ст­руи­ро­вания би­то­вых строк [Bitstring Comprehensions] невоз­мож­но.

За­да­ча по под­сче­ту ко­ли­че­­ст­ва ве­ду­щих бит со зна­чением 0 ре­ша­ет­ся в сле­дую­щих двух функ­ци­ях: head_unsetbit_count/1 и head_unsetbit_count/2. Пер­вая функ­ция яв­ля­ет­ся ин­тер­фейс­ной, вто­рая функ­ция реа­ли­зу­ет ал­го­ритм по под­сче­ту ко­ли­че­­ст­ва ве­ду­щих бит со зна­чением 0; усло­ви­ем окон­чания ра­бо­ты яв­ля­ет­ся факт по­яв­ления би­та со зна­чением 1 на мес­те об­ра­ба­ты­вае­мо­го, ли­бо об­ра­бот­ка всей би­то­вой стро­ки.

head_unsetbit_count(Bitstring) when is_bitstring(Bitstring) ->

head_unsetbit_count(Bitstring, 0).

head_unsetbit_count(<<>>, Count) -> Count;

head_unsetbit_count(<<0:1, Rest/bitstring>>, Count) ->

head_unsetbit_count(Rest, Count + 1);

head_unsetbit_count(<<1:1, _Rest/bitstring>>, Count) -> Count.

За­да­ча по под­сче­ту ко­ли­че­­ст­ва за­вер­шаю­щих бит со зна­чением 0 ре­ша­ет­ся в сле­дую­щих двух функ­ци­ях: tail_unsetbit_count/1 и tail_unsetbit_count/2. Как и во всех по­доб­ных за­да­чах, пер­вая функ­ция яв­ля­ет­ся ин­тер­фейс­ной, а вто­рая реа­ли­зу­ет ал­го­ритм за­да­чи. От­ли­чие этой за­да­чи от пре­ды­ду­щей за­клю­ча­ет­ся в том, с ка­ко­го кон­ца би­то­вой стро­ки бе­рут­ся би­ты на об­ра­бот­ку. В пре­ды­ду­щей за­да­че мы бра­ли би­ты с на­ча­ла би­то­вой стро­ки, а в те­ку­щей за­да­че – с кон­ца би­то­вой стро­ки. Когда мы ре­кур­сивно об­ра­ба­ты­ва­ем би­то­вую стро­ку с на­ча­ла, раз­де­ляя ее на сег­мент и оста­ток, то в этом слу­чае мы име­ем доста­точ­но про­стое вы­ра­жение со­от­вет­ст­вия шаб­ло­ну, т. к. мы мо­жем не за­да­вать раз­мер остат­ка. Когда мы ре­кур­сив­но об­ра­ба­ты­ва­ем би­то­вую стро­ку с кон­ца, раз­де­ляя ее на сег­мент и оста­ток, то в этом слу­чае вы­ра­жение со­от­вет­ст­вия шаб­ло­ну бо­лее слож­ное, т. к. мы обя­за­ны вы­чис­лить и за­дать раз­мер остат­ка яв­но. Разницу в реа­ли­за­ции об­ра­бот­ки би­то­вой стро­ки с на­ча­ла и с кон­ца мож­но уви­деть в реа­ли­за­ции пре­ды­ду­щей и те­ку­щей за­дач (в ка­че­­ст­ве со­ве­та: когда есть та­кая воз­мож­ность, всегда реа­ли­зуй­те об­ра­бот­ку би­то­вой стро­ки с ее на­ча­ла).

tail_unsetbit_count(Bitstring) when is_bitstring(Bitstring) ->

tail_unsetbit_count(Bitstring, 0).

tail_unsetbit_count(<<>>, Count) -> Count;

tail_unsetbit_count(Bitstring, Count) ->

RestSize = bit_size(Bitstring) - 1,

<<Rest:RestSize/bitstring, TailBit:1>> = Bitstring,

case TailBit of

0 -> tail_unsetbit_count(Rest, Count + 1);

1 -> Count

end.

Как обыч­но, по­сле реа­ли­за­ции за­да­чи про­ве­рим пра­виль­ность этой реа­ли­за­ции. В би­то­вой стро­ке <<2#000110000:9>> – 3 ве­ду­щих би­та со зна­чением 0 и 4 за­вер­шаю­щих би­та со зна­чением 0. Пусть пе­ре­мен­ная Bitstring со­дер­жит зна­чение <<2#000110000:9>>; тогда вы­зов bit_utils:head_unsetbit_count(Bitstring) воз­вра­ща­ет 3, а вы­зов bit_utils:tail_unsetbit_count(Bitstring) воз­вра­ща­ет 4.

В ка­че­­ст­ве по­следней за­да­чи на се­го­дня, рас­смот­рим за­да­чу ин­вер­ти­ро­вания со­дер­жи­мо­го би­то­вой стро­ки. Эту за­да­чу мож­но ре­шить дву­мя раз­ны­ми спо­со­ба­ми: с ис­поль­зо­ванием хво­сто­вой ре­кур­сии и с ис­поль­зо­ванием вы­ра­жений кон­ст­руи­ро­вания би­то­вых строк [Bitstring Comprehensions].

Да­вай­те ре­шим эту за­да­чу с ис­поль­зо­ванием вы­ра­жений кон­ст­руи­ро­вания би­то­вых строк; оче­вид­но, что вы­ра­жение по­лу­чит­ся три­ви­аль­ное, т. к. у нас толь­ко один ис­точник, из ко­то­ро­го мы бу­дем доста­вать дан­ные сег­мен­та­ми раз­ме­ром в 1 бит, и от­сут­ст­ву­ют ка­кие-ли­бо фильт­ры.

Един­ст­вен­ный мо­мент, ко­то­рый мо­жет вы­звать во­прос – это как по­лу­чить ин­вер­ти­ро­ван­ное зна­чение би­та. В язы­ке Erlang есть опе­ра­тор bnot, ко­то­рый яв­ля­ет­ся по­би­то­вым опе­ра­то­ром «НЕ». Это оз­на­ча­ет, что bnot 0 ра­вен -1, а bnot 1 ра­вен -2. Конеч­но, мож­но ис­поль­зо­вать и этот опе­ра­тор с уче­том об­ре­зания зна­чения до од­но­го би­та, когда мы бу­дем соз­да­вать сег­мент раз­ме­ром 1 бит. Но мы вос­поль­зу­емся дру­гим би­то­вым опе­ра­тором, ко­то­рый без вся­ко­го об­ре­зания по­зво­ля­ет нам ин­вер­ти­ро­вать зна­чения би­тов: это по­би­то­вый опе­ра­тор «ИСКЛЮЧАЮЩЕГО ИЛИ» или bxor.

inverse(Bitstring) when is_bitstring(Bitstring) ->

<< <<(Bit bxor 1):1>> || <<Bit:1>> <= Bitstring >>.

Ос­та­лось толь­ко про­ве­рить пра­виль­ность реа­ли­за­ции на­ше­го ал­го­рит­ма: для би­то­вой стро­ки <<2#01101001>> ин­вер­ти­ро­ван­ное зна­чение бу­дет <<2#10010110>> или <<150>>. Вы­зов bit_utils:inverse(<<2#01101001>>) воз­вра­ща­ет <<150>>.

Что­бы все при­ве­ден­ные здесь при­ме­ры ра­бо­та­ли, необ­хо­ди­мо ор­ганизо­вать их в мо­дуль и соз­дать спи­сок экс­пор­ти­руе­мых функ­ций. При­ве­ден­ные ниже стро­ки де­ла­ют это (и не за­бы­ва­ем, что имя фай­ла долж­но быть имя мо­ду­ля с рас­ши­рением “.erl”):

-module(bit_utils).

-export([reverse_bytes/1, reverse_bits/1]).

-export([integer_size/1, integer_signed_size/1, integer_to_binary/3]).

-export([setbit_count/1, head_unsetbit_count/1, tail_unsetbit_count/1, inverse/1]).

Се­го­дня мы ис­поль­зо­ва­ли «чер­ную ма­гию» би­то­вых строк для ре­шения неболь­ших за­дач, свя­зан­ных с ра­бо­той с це­лы­ми чис­ла­ми и би­то­вы­ми стро­ка­ми. Ов­ла­дение этой «ма­ги­ей» по­зво­ля­ет ре­шать мно­гие та­кие за­да­чи бы­ст­ро, кра­си­во и эф­фек­тив­но. Но мы не за­кан­чи­ва­ем прак­ти­кум по би­то­вым стро­кам. В сле­дую­щей ста­тье мы рас­смот­рим ис­поль­зо­вание би­то­вых строк на го­раз­до боль­шем при­ме­ре.


Источник — «http://wiki.linuxformat.ru/wiki/index.php?title=LXF155:%D0%92%D0%BD%D0%B8%D0%BA%D0%B0%D1%82%D1%8C_%D0%B2_Erlang&oldid=16472»
Персональные инструменты
купить
подписаться
Яндекс.Метрика