Actually, microoptimizing _power_of_two is a red herring and the problem is the quadratic complexity of _decompose (_value2member_map_ becomes bigger and bigger at each iteration).  Replacing the implementation of _decompose by the following fixes the performance issue (the original snippet executes in ~150ms, which may be even more optimizable but already a 30x improvement :)), and still passes test_enum.py (from cpython 3.7.4):


    def _decompose(flag, value):
        """Extract all members from the value."""
        # _decompose is only called if the value is not named
        not_covered = value
        members = []
        for member in flag:
            member_value = member.value
            if member_value and member_value & value == member_value:
                members.append(member)
                not_covered &= ~member_value
        if issubclass(flag, IntFlag) and value > 0:
            while not_covered:
                new_value = 2 ** _high_bit(not_covered)
                if new_value not in flag._value2member_map_:
                    # construct singleton pseudo-members
                    pseudo_member = int.__new__(flag, value)
                    pseudo_member._name_ = None
                    pseudo_member._value_ = value
                    flag._value2member_map_.setdefault(value, pseudo_member)
                members.append(flag(new_value))
                not_covered &= ~new_value
        if not members and value in flag._value2member_map_:
            members.append(flag._value2member_map_[value])
        members.sort(key=lambda m: m._value_, reverse=True)
        if len(members) > 1 and members[0].value == value:
            # we have the breakdown, don't need the value member itself
            members.pop(0)
        return members, not_covered


Checking for issubclass(flag, IntFlag) is a bit ugly but that's because Flag and IntFlag really need two separate implementations of _decompose -- the former wants to error out on uncovered values, the latter should create them on-the-fly.