Is it possible to optimize the lexicographic successor function?

Question

When using bitstring the "ORDER BY" is the lexicographic order. For example ordering all bitstrings, from 1 to 4 bits:

 0
 00
 000
 001
 01
 010
 011
 1
 10
 100
 101
 11
 110
 111

The successor function of a maximum of k bits, succ_lex(x,k), in this context, must return "the next value" of the lexicographical order: succ_lex('0',3)=b'00';   succ_lex('01',3)=b'010';   succ_lex('010',3)=b'011';  ...

I need a faster solution.

Slow solution

Using a naive algorithm.

CREATE FUNCTION vbit_cutlast1s(p_x varbit) RETURNS varbit AS $f$
  SELECT CASE
    WHEN len>0 AND get_bit(p_x,len-1)::boolean THEN vbit_cutlast1s( substring(p_x,1,len-1) )
    ELSE CASE WHEN len=0 THEN ''::varbit ELSE substring(p_x,1,len-1) || '1'::bit(1) END
    END
  FROM (SELECT length(p_x)) t(len)
$f$ LANGUAGE SQL IMMUTABLE;
COMMENT ON FUNCTION vbit_cutlast1s(varbit)
  IS 'Cuts last 1s and replace remaining zero (or empty) by 1.'
;
CREATE FUNCTION vbit_succ_lex(p_x varbit, p_bits int DEFAULT 64) RETURNS varbit AS $f$
  SELECT CASE
    WHEN length(p_x)<p_bits THEN p_x || '0'::bit(1)
    ELSE vbit_cutlast1s(p_x)
    END
$f$ LANGUAGE SQL IMMUTABLE;
COMMENT ON FUNCTION vbit_succ_lex(varbit,int)
  IS 'Lexicographical successor limited by k, based on cutlast1s().'
;

Testing:

DO $tests$
begin
  ASSERT vbit_succ_lex('',3) = b'0',      'T1';
  ASSERT vbit_succ_lex('0',3) = b'00',    'T2';
  ASSERT vbit_succ_lex('01',3) = b'010',  'T3';
  ASSERT vbit_succ_lex('010',3) = b'011', 'T4';
  ASSERT vbit_succ_lex('00111',5) = b'01','T5';
  ASSERT vbit_succ_lex('01111',5) = b'1', 'T6';
  ASSERT vbit_succ_lex('111',3) = b'',    'T7';
end;
$tests$ LANGUAGE plpgsql;