Замена первого и последнего бита в числе

Например, так:

unsigned int chg(unsigned int n)
{
    if (n && ((n&1) == 0))
    {
        unsigned int i = -1;
        for(unsigned int m = n; m; m >>= 1, i++);
        n = (n & ~(1<<i))|1;
    }
    return n;
}

По сути, надо только одно - в четном числе сбросить старший бит, и младший сделать 1.

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

Для эффективного поиска этого бита компиляторы предоставляют встроенные функции. Например, в gcc (g++) это __builtin_clz() и __builtin_clzl(), которые возвращают количество лидирующих нулевых бит для 32 и 64 разрядных чисел (их эквиваленты для windows MSVC).

На их основе можно написать пару удобных макросов, возвращающих осмысленный резульат (типа int) для любого (long long, long, int, short и char) целого типа.

Первый макрос возвращает количество лидирующих нулей (в т.ч. и для числа, равного 0)

#define CLZ(X) ({int _n = sizeof(X); typeof(X) _x = X;                                            \
                 unsigned long long _ul = _n < sizeof(long long) ?                                \
                       (_x & ((1ULL << (_n * CHAR_BIT)) - 1)) : _x;                               \
                 _ul ? __builtin_clzl(_ul) - ((int)sizeof(long long) * CHAR_BIT - CHAR_BIT * _n)  \
                       : CHAR_BIT * _n;})

(обратите внимание, выражение вида (1 << n) - 1 создает битовую маску из n единичных бит, применение которой оставляет значимыми n младших бит числа)

Второй возвращает позицию (считая с нуля) самого старшего бита, равного 1 (или -1 для числа, равного 0)

#define FSB(X) ({int _n = sizeof(X), _b = CLZ(X); _n * CHAR_BIT - _b - 1;})

(константа CHAR_BIT обычно определена в <limits.h>)

Небольшой пример

int
main (int ac, char *av[])
{
  printf("FSB(0) = %d\n", FSB(0));
  printf("FSB((char)-1) = %d\n", FSB((char)-1));
  printf("FSB(-1LL) = %d\n", FSB(-1LL));
  printf("FSB(5) = %d\n", FSB(5));

  return puts("End") == EOF;
}

Выдает на печать

avp@avp-desktop:~/avp/hashcode$ gcc ttt.c -O3 -Wall
avp@avp-desktop:~/avp/hashcode$ ./a.out
FSB(0) = -1
FSB((char)-1) = 7
FSB(-1LL) = 63
FSB(5) = 2
End
avp@avp-desktop:~/avp/hashcode$ 

Надеюсь, описанные приемы окажутся вам полезны.

Во-первых, первый бит - всегда 1 (ну если число не 0), так что для нечётных чисел ничего менять не надо. А вот для чётных - надо стереть старший бит и присобачить последнюю 1.

Работает только с беззнаковыми типами: https://ideone.com/6m12Pd

#include <iostream>
 
using namespace std;
 
template <typename T> T f(T x)
{
  if (!x || x & 1)
    return x;
 
  T m = ~(T)0;
  for (; m > x; m >>= 1);
  return x ^ (m<<1) ^ m;
}
 
int main()
{
  for (unsigned x; cin >> x; )
    cout << x << ' ' << f(x) << endl;
 
  unsigned long long y = -2ULL;
  cout << y << ' ' << f(y) << endl;
 
  return 0;
}

Версия для Си: https://ideone.com/LNEnzc

#include <stdio.h>
 
#define F(T, suf) T f_##suf(T x)  \
{                                 \
  if (!x || x & 1)                \
    return x;                     \
                                  \
  T m = ~(T)0;                    \
  for (; m > x; m >>= 1);         \
  return x ^ (m<<1) ^ m;          \
}
 
F(unsigned, u)
F(unsigned long long, ull)
 
int main()
{
  unsigned x;
 
  while (scanf("%u", &x) == 1)
    printf("%u %u\n", x, f_u(x));
 
  unsigned long long y = -2LLU;
  printf("%llu %llu\n", y, f_ull(y));
 
  return 0;
}

И модифицированная версия на Си: https://ideone.com/DSx3I9

#include <stdio.h>
 
#define F(T, suf) T f_##suf(T x)  \
{                                 \
  if (!x || x & 1)                \
    return x;                     \
                                  \
  for (unsigned i=0; ; ++i)       \
    if ((x>>i) == 1)              \
      return x ^ (x>>i<<i) | 1;   \
}
 
F(unsigned, u)
F(unsigned long long, ull)
 
int main()
{
  unsigned x;
 
  while (scanf("%u", &x) == 1)
    printf("%u %u\n", x, f_u(x));
 
  unsigned long long y = -2LLU;
  printf("%llu %llu\n", y, f_ull(y));
 
  return 0;
}

Результат:

0 0
1 1
2 1
3 3
4 1
7 7
8 1
9 9
10 3
14 7
12345 12345
132456 1385
18446744073709551614 9223372036854775807