frage zu bestimmtes bit setzen

[pepe75]

hallo,
ich schreibe gerade ein poker-programm in C++ und haette gerne gewusst, ob ihr ne Idee zu folgendem Bit-Setz-Problem habt:

in einem Bitmuster (welches nicht null ist) soll ein bestimmtes Null-Bit gesetzt werden, undzwar dasjenige welches am weitesten links (most significant bit) liegt es jedoch noch gesetzte Bits links gibt:

Beispiel(e)

0011 0110 --> 0011 1110
1011 0110 --> 1111 0110
0000 0110 --> 0000 0111

vielen dank.

[pepe75]

eine zusaetzliche anforderung ist es,
das ganze moeglichst schnell durchzufuehren, ein ellen-langer-algo waere nicht so toll.
danke.

[Tachyon]

Und bei sowas:
0100 1000?

[zwutz]

ich werd aus deiner Beschreibung nicht wirklich schlau und auch deine Beispiele sind nichtssagend, da dort nirgends das MSB geaendert wird

[Fellhuhn]

Häßlich aber schnell. Ein paar andere Algorithmen findest du hier

static const char LogTable256[] = 
{
  0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};

unsigned int v = old_value; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

unsigned int new_value;
do{
  new_value = old_value | pow(2, (--r));
while(r >= 0 && new_value == old_value);

[pepe75]

Tachyon schrieb:

Und bei sowas:
0100 1000?

wuerde 0110 1000 ergeben.

zwutz schrieb:

ich werd aus deiner Beschreibung nicht wirklich schlau und auch deine Beispiele sind nichtssagend, da dort nirgends das MSB geaendert wird

soll ja auch nicht. die beschreibung welches bit gesetzt werden soll ist in der tat umgangsprachlich etwas schwierig, versuche es aber nochmal

Finde die am weitesten links liegende Bitposition an der ein Null-Bit vorzufinden ist, jedoch links von dieser position mindestens noch eine 1 vorzufinden ist.

ich gehe hier beispielhaft von 32-bit-zahlen aus und davon dass das zu untersuchende bitmuster zahlenmaessig keine Null ist.

danke.

[pepe75]

Fellhuhn schrieb:

Häßlich aber schnell. Ein paar andere Algorithmen findest du hier

static const char LogTable256[] = 
{
  0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
  7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
};

unsigned int v = old_value; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
  r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else 
{
  r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

unsigned int new_value;
do{
  new_value = old_value | pow(2, (--r));
while(r >= 0 && new_value == old_value);

UPS, ... ähm, ist natuerlich schoen, wenn obiges tatsaechlich das macht was ich beschrieben habe (und das vielleicht noch schnell??). Vorraussetzung hierfuer ist jedoch das Du mein Problem verstanden hast (oder ich es ausreichend hervorbringen konnte) -> macht obiges wirklich das, was ich will?!?

danke.
gruss.

[Fellhuhn]

Sollte.

EDIT:

Im Grunde rechnet er dort log_2(value) und geht dann schrittweise die bits zurück um zu schauen ob sich noch eine 0 weiter rechts finden läßt und setzt die dann.

[zwutz]

jetzt blick ich durch... mich hat dein Hinweis auf das MSB irritiert, da das wirklich _nur_ das MOST Signigficant Bit bezeichnet und danach ja logischerweise nichts mehr kommen kann

was ist aber bei 0000 0001?

[pepe75]

zwutz schrieb:

jetzt blick ich durch... mich hat dein Hinweis auf das MSB irritiert, da das wirklich _nur_ das MOST Signigficant Bit bezeichnet und danach ja logischerweise nichts mehr kommen kann
was ist aber bei 0000 0001?

stimmt ist ein sonderfall, ich wuerd sagen dass ding bleibt unveraendert
danke.

[Belli]

[quote="pepe75"]
UPS, ... ähm, ist natuerlich schoen, wenn obiges tatsaechlich das macht was ich beschrieben habe (und das vielleicht noch schnell??). Vorraussetzung hierfuer ist jedoch das Du mein Problem verstanden hast (oder ich es ausreichend hervorbringen konnte) -> macht obiges wirklich das, was ich will?!?
/quote]

Wenn ich das hier so schön serviert bekäme, würde ich es einfach ausprobieren, und mich melden, wenn es nicht so funktionieren würde, wie ich wollte ...

[camper]

Fellhuhn schrieb:

Sollte.

EDIT:

Im Grunde rechnet er dort log_2(value) und geht dann schrittweise die bits zurück um zu schauen ob sich noch eine 0 weiter rechts finden läßt und setzt die dann.

pow(2, foo ?
warum enthält die LUT nicht gleich die gesuchte Bitstelle?

template <unsigned v>
struct strange_bit_scan
{
    static const int value = v % 2 == 0 || strange_bit_scan< v / 2 >::value != -1 ? 1 + strange_bit_scan< v / 2 >::value : -1;
};

template <>
struct strange_bit_scan< 0 >
{
    static const int value = -1;
};

kann man trivial zum generieren einer LUT benutzen.